알못에서 잘알까지

    31번 문제   

    내가 풀이한 답   

 CaHb(1<=a=b<=100)와 같이 형식이 정해져 있으므로 단순하게 생각했다. 처음 C는 모두 공통이라 생각했고 H의 인덱스에 따라서 a와 b 값을 구하고 a에는 12를 b에는 1을 곱해서 둘이 더하는 방법을 사용하였다. 

#include <stdio.h>
#include <cstring>

char arr[8];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	scanf("%s", &arr);
	
	int i, k = 1, idx, temp, res;
	
	for(i=1; i<strlen(arr); i++){
		if(arr[i] == 'H') idx = i;
	}
	
	if(idx == 1) temp = 12;
	else {
		for(i=idx-1; i>0; i--){
			temp += (arr[i]-'0') * k;
			k *= 10;
		}
		temp *= 12;
	}
	
	if(idx == strlen(arr) -1) res += 1;
	else {
		k = 1;
		for(i=strlen(arr)-1; i>idx; i--){
			res += (arr[i]-'0') * k;
			k *= 10;
		}
	}
	
	res += temp;
	printf("%d", res);
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
int main(){
	//freopen("input.txt", "rt", stdin);
	char a[10];
	int c=0, h=0, i, pos;
	scanf("%s", &a);
	if(a[1]=='H'){
		c=1;
		pos=1;
	}
	else{
		for(i=1; a[i]!='H'; i++){
			c=c*10+(a[i]-48);
		}
		pos=i;
	}
	if(a[pos+1]=='\0') h=1;
	else{
		for(i=pos+1; a[i]!='\0'; i++){
			h=h*10+(a[i]-48);
		}
	}
	printf("%d\n", c*12+h);	
	return 0;
}

  사이트의 답도 H를 기준으로 코드를 짠 것을 확인하였다. 

    30번 문제   

    내가 풀이한 답   

  앞의 문제와 동일한 코드로 채점해봤지만 역시 Time_Limit이 났다. 

#include <stdio.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, i, temp, cnt=0;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		temp=i;
		while(temp>0){
			if(temp%10==3) cnt++;
			temp /= 10;
		}
	}
	
	printf("%d", cnt);
	
	return 0;
}

 순회문(for, while) 하나로 작성하기에는 어떤 특정한 논리가 필요한데 생각나지 않아서 강의 초반부를 참고했다. 논리는 다음과 같다. 

 핵심은 자리 수를 기준으로 입력받은 수를 left, cur, right로 구분하고 cur의 숫자에 따라 공식이 달라진다는 것이다. 위의 아래 그림에서 k가 10이므로 cur은 10의 자리 숫자를 가리킨다.(아래 그림에선 각각 7, 3, 1) 이 cur을 기준으로 왼쪽은 left, 오른쪽은 right로 설정한다. 그리고 cur을 기준으로 공식을 설정한다. 

 4377을 예로 들면 흐름은 다음과 같다. 

    사이트의 답안   

#include<stdio.h>
int main(){
	//freopen("input.txt", "rt", stdin);
	int n, left=77, right, cur, k=1, res=0;
	scanf("%d", &n);
	
    while(left != 0){
		left=n/(k*10);
		right=n%k;
		cur=(n/k)%10;
		if(3<cur){
			res=res+((left+1)*k);
		}
		else if(3==cur){
			res=res+((left*k)+(right+1));
		}
		else res=res+(left*k);	
		k=k*10;
	}
	
    printf("%d\n", res);
	return 0;
}

    29번 문제   

    내가 풀이한 답   

 n번 순회(for)를 돌며 i번째 수가 10으로 나눈 나머지가 3이면 값을 증가시키는 방법을 사용하였다. 

#include <stdio.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, i, temp, cnt=0;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		temp=i;
		while(temp>0){
			if(temp%10==3) cnt++;
			temp /= 10;
		}
	}
	
	printf("%d", cnt);
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
	freopen("input.txt", "rt", stdin);
	int n, tmp, i, cnt=0, digit;
	scanf("%d", &n);
    
	for(i=1; i<=n; i++){
		tmp=i;
		while(tmp>0){
			digit=tmp%10;
			if(digit==3) cnt++;
			tmp=tmp/10;
		}
	}
    
	printf("%d\n", cnt);
	return 0;
}

  사이트의 답과 논리적으로 일치하였음을 확인했다.

    28번 문제   

    내가 풀이한 답   

 전 문제인 27번 문제와 상당히 유사하다고 생각했다. 일의 자리부터 0이 연속적으로 몇 개 있는지 알려면 2로 소인수분해 했을 때의 개수와 5로 소인수분해 했을 때의 개수가 필요하다고 생각했고 둘 중 작은 값이 0의 개수라고 생각하고 코드를 짰다. 

#include <stdio.h>

int arr[6];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, i, temp, j;
	scanf("%d", &n);
	
	for(i=2; i<=n; i++){
		temp=i, j=2;
		while(j<6){
			if(temp%j==0){
				arr[j]++;
				temp /= j;
			}
			else j++;
		}
	}
	
	if(arr[2] <= arr[5]) printf("%d", arr[2]);
	else printf("%d", arr[5]);
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	freopen("input.txt", "rt", stdin);
	int n, i, j, tmp, cnt1=0, cnt2=0;
	scanf("%d", &n);
    
	for(i=2; i<=n; i++){
		tmp=i;
		j=2;
		while(1){
			if(tmp%j==0){
				if(j==2) cnt1++;
				else if(j==5) cnt2++;
				tmp=tmp/j;
			}
			else j++;
			if(tmp==1) break;
		}
	}
    
	if(cnt1<cnt2) printf("%d\n", cnt1);
	else printf("%d\n", cnt2);
	return 0;
}

  사이트의 답은 2의 개수와 5의 개수를 따로 변수를 설정하였다. 핵심적인 논리는 2와 5의 개수를 찾는 것으로 똑같았다. 

    27번 문제   

    내가 풀이한 답   

 문제를 읽고 소인수분해를 이용하여 풀어야겠다는 생각을 했다. 입력값의 범위가 작다보니 순회(for, while)문을 중첩해도 상관없다고 생각하고 코드를 짯다. 

 핵심은 소수로 표현할 때 소수의 범위는 n을 넘지 않는 다는 것이다. 따라서, n크기의 배열을 생성하여 각각의 수들을 소인수분해 하고 해당 배열의 인덱스를 증가시켜주는 방법이다. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int n, i, j, temp;
	scanf("%d", &n);
	
	int *arr = (int *)malloc(sizeof(int) * (n+1));
	memset(arr, 0, sizeof(int)* (n+1));
	
	for(i=2; i<=n; i++){
		temp=i, j=2;
		while(temp>1){
			if(temp%j==0){
				arr[j]++;
				temp /= j;
			}
			else j++;
		}
	}
	
	printf("%d! = ", n);
	for(i=2; i<=n; i++){
		if(arr[i] != 0) printf("%d ", arr[i]);
	}

	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
	int n, i, j, tmp;
	scanf("%d", &n);
	vector<int> ch(n+1);
    
	for(i=2; i<=n; i++){
		tmp=i;
		j=2;
		while(1){
			if(tmp%j==0){
				ch[j]++;
				tmp=tmp/j;
			}
			else j++;
			if(tmp==1) break;
		}
	}
    
	printf("%d! = ", n);
	for(j=2; j<=n; j++){
		if(ch[j]!=0) printf("%d ", ch[j]);
	}
    
	return 0;
}
				
		

  사이트의 답과 똑같은 논리임을 확인하였다.

    26번 문제   

    내가 풀이한 답   

 N명의 선수 중 맨 앞에(Index 0) 있는 선수는 1로 고정이고 그 뒤에 있는 선수들은 Index + 1에 해당하는 수에서 앞의 선수들보다 값이 크다면 하나씩 감소하는 방법으로 코드를 짰다.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, i, j, temp=0;
	scanf("%d", &n);
	int *arr = (int *)malloc(sizeof(int) * n);
	
	for(i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	
	printf("%d ", 1);
	
	for(i=1; i<n; i++){
		temp = i+1;
		for(j=i-1; j>=0; j--){
			if(arr[i] > arr[j]) temp--;
		}
		printf("%d ", temp);
	}
	
	free(arr);
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	freopen("input.txt", "rt", stdin);
	int i, j, n, cnt=0;
	scanf("%d ", &n);
	vector<int> a(n+1);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	printf("1 ");
	for(i=2; i<=n; i++){
		cnt=0;
		for(j=i-1; j>=1; j--){
			if(a[j]>=a[i]) cnt++;
		}
		printf("%d ", cnt+1);
	}
	return 0;
}

  사이트의 답은 index + 1이 아닌 0부터 시작하여 증가하였음을 확인하였다. 

    25번 문제   

    내가 풀이한 답   

  문제도 짧고 흔할 것 같이 생긴 문제였다. 당장 생각나는 것은 입력받은 값들을 순회(for)를 돌면서 그 순회 속에 순회(for)를 돌아서 전것들과 비교하면서 하는 것이였다. 하지만, 요즘 Time Limit을 신경쓰고 있어서 그런지 이중 순회(for)를 안쓰려고 했다. 

 그래서 생각해낸 방법은 입력 받은 수들을 배열(a)에 저장하고 그 값들을 또 새로운 배열(b)에 저장한다. 배열 a를 다시 sort 함수를 이용해 오름차순으로 정렬하고 다음 값과 같지 않으면 전체 인원 - 인덱스를 빼준다. 이러면, 다음 값이 같은 값이여도 등수문제를 해결할 수 있다.

 이중 순회(for)를 안써서 시간상으로는 조금 더 빠르겠지만 메모리를 많이 잡아먹는 다는 단점과 라이브러리를 많이 사용한다는 단점이 있다. 

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
using namespace std;

int c[101];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, i;
	scanf("%d", &n);
	
	int *a = (int *)malloc(sizeof(int) * (n+1));
	int *b = (int *)malloc(sizeof(int) * (n+1));
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);	
	}
	
	memcpy(b, a, sizeof(int)*(n+1));
	sort(a, a+n);
	
	for(i=0; i<n; i++){
		if(a[i] != a[i+1]){
			c[a[i]] = n-i;
		}
	}
	
	for(i=0; i<n; i++){
		printf("%d ", c[b[i]]);
	}
	
	free(a);
	free(b);	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
int main(){
	//freopen("input.txt", "rt", stdin);
	int i, j, a[200], b[200], n;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
		b[i]=1;
	}
    
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			if(a[j]>a[i]) b[i]++;
		}
	}
    
	for(i=1; i<=n; i++){
		printf("%d ", b[i]);
	}
	return 0;
}

  사이트의 답은 맨 처음 생각했던 방식이 나왔다. 입력 값의 범위가 크지 않으므로 이중 순회(for)를 돌아도 문제가 없었다. 

    24번 문제   

    내가 풀이한 답   

  배열 두 개를 가지고 코드를 짜 보았다. a 배열은 순전히 입력된 수만 저장하는 배열이고 b 배열은 인접한 두 수의 차이의 절대값을 index로 삼아 값을 바꿔주었다. 그래서 0이 아닌 값이 존재하면 유쾌한 점퍼(jolly jumper)가 아니므로 NO를 출력하고 모두 0이면 YES를 출력한다.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int n, i, temp;
	bool flag = true;
	scanf("%d", &n);
	
	int *a = (int *)malloc(sizeof(int)*n);
	int *b = (int *)malloc(sizeof(int)*n);
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	
	for(i=0; i<n-1; i++){
		temp = abs(a[i+1]-a[i]);
		b[temp] = 0;
	}
	
	for(i=1; i<n; i++){
		if(b[i]!=0){
			flag = false;
			break;
		}
	}
	
	if(flag) printf("%s", "YES");
	else printf("%s", "NO");
	
	free(a);
	free(b);

	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n, i, now, pre, pos;
	scanf("%d", &n);
	vector<int> ch(n);
	scanf("%d", &pre);
    
	for(i=1; i<n; i++){
		scanf("%d", &now);
		pos=abs(pre-now);
		if(pos>0 && pos<n && ch[pos]==0) ch[pos]=1;
		else{
			printf("NO\n");
			return 0;
		}
		pre=now;
	}
    
	printf("YES\n");
	return 0;
}

  사이트의 답은 두 값의 차이의 절대값이 총 개수-1의 범위안에 있는지와 중복의 유무가 핵심이였다. 전 값 pre와 다음 값 now를 선언하고 두 값의 차이의 절대값을 pos 변수로 두었다. 제일 첫 번째 값을 pos로 입력을 받은 뒤 순회(for)를 돌며 절대값을 구하고 절대값이 총 개수보다 작은지를 판별하고 벡터의 pos 인덱스가 0인지를 확인하며 중복을 검사한다. 중복 값이 있다는 것은 나머지 부분에 무조건 공백이 존재한다는 것을 말해준다. 검사가 끝나면 pre값을 now로 바꿔주고 순회를 이어간다. 순회를 마치면 모든 값이 존재하므로 유쾌한 점퍼(Jolly Jumpers)가 된다.

    23번 문제   

    내가 풀이한 답   

  순회(for)를 돌면서 i번째 값과 i+1값을 비교하여 증가하는 값이거나 같은 값이면 len 변수를 증가시키는 방향으로 코드를 짰다. 감소하는 값이면 len 변수를 다시 0으로 초기화하였다.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int n, i, len = 0, max = 0;
	scanf("%d", &n);
	
	int *arr = (int *)malloc(sizeof(int)* n);
	
	for(i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	
	for(i=0; i<n-1; i++){
		if(arr[i+1]-arr[i] >= 0){
			len++;
			if(len > max) max = len;
		}
		else len = 0;
	}
	
	printf("%d", max+1);
	free(arr);
    	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>			
int main(){
	freopen("input.txt", "rt", stdin);
	int n, i, pre, now, cnt, max;
	scanf("%d", &n);
	scanf("%d", &pre);
	cnt=1;
	max=1;
	for(i=2; i<=n; i++){
		scanf("%d", &now);
		if(now>=pre){
			cnt++;
			if(cnt>max) max=cnt;
		}
		else cnt=1;
		pre=now;
	}
	printf("%d\n", max);	
	return 0;
}

  사이트의 답은 배열을 사용하지 않고 차례대로 입력한 값을 바탕으로 진행하였다. 논리적으로는 똑같은 것을 확인했다. 

    22번 문제   

    내가 풀이한 답   

  처음에는 이중 순회(for)를 돌아서 코드를 짰다. 하지만 입력값이 10만 이하인 것을 보고 안될것이라고 예상은 했다. 돌려봤지만 역시나 Time Limit이였고 이중 순회를(for) O(루트 N)이나 O(N)으로 접근하는 다른 방법이 필요했다. 곰곰히 생각해보았지만 답이 떠오르지 않아서 강의 초반부를 들었다. 강의를 들었을 때 머리를 뒤통수로 한대 맞은 듯한 느낌이 들었다. 

 원리의 핵심은 다음과 같다. 초기값으로 연속적인 며칠에 해당하는 K동안의 합을 구한다. 그리고 그 초기값을 바탕으로 K번째부터 순회(for)를 돌아 K번째에 해당하는 값은 더하고 그 인덱스(처음은 K)에 K값을 뺀 인덱스의 값을 빼준다는 것이다. 

#include <stdio.h>
#include <stdlib.h>


int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int n, k, i, temp = 0, max = 0;
	scanf("%d %d", &n, &k);

	int *arr = (int *)malloc(sizeof(int) * n);
	
	for(i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	
	for(i=0; i<k; i++){
		temp += arr[i];
		max = temp;
	}
	
	for(i=k; i<n; i++){
		temp = temp + arr[i] - arr[i-k];
		if(temp > max) max = temp;
	}
	
	printf("%d", max);
	
	free(arr);
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
using namespace std;			
int main(){
	freopen("input.txt", "rt", stdin);
	int n, k, i, sum=0, res;
	scanf("%d %d", &n, &k);
	vector<int> a(n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	for(i=0; i<k; i++){
		sum=sum+a[i];
	}
	res=sum;
	for(i=k; i<n; i++){
		sum=sum+(a[i]-a[i-k]);
		if(sum>res) res=sum;
	}
	printf("%d\n", res);
	return 0;
}

  사이트의 답은 벡터를 사용하였다. 벡터에 대해 정리해보는 시간을 가져야겠다.