알못에서 잘알까지

    21번 문제   

    내가 풀이한 답   

  문제는 상당히 길었는데 읽고 보면 조건문 몇 개만 추가해주면 되겠다는 감이 왔다. A의 총점 변수와 B의 총점 변수 그리고 비겼을 때 라운드를 제외하고 승부가 판가름이 난 final 변수를 이용해서 코드를 짜보았다. 

#include <stdio.h>

int a[10];
int b[10];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int i, sumA=0, sumB=0, final;
	
	for(i=0; i<10; i++){
		scanf("%d", &a[i]);
	}
	
	for(i=0; i<10; i++){
		scanf("%d", &b[i]);
	}
	
	for(i=0; i<10; i++){
		if(a[i] > b[i]) {
			sumA+=3;
			final = i;
		}
		else if(a[i] < b[i]) {
			sumB+=3;
			final = i;
		}
		else {
			sumA+=1;
			sumB+=1;
		}
	}
	
	printf("%d %d\n", sumA, sumB);
	
	if(sumA > sumB) printf("%c", 'A');
	else if(sumA < sumB) printf("%c", 'B');
	else {
		if(a[final] == b[final]) printf("%c", 'D');
		else {
			if(a[final] > b[final]) printf("%c", 'A');
			else printf("%c", 'B');
		}
	}
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>			
int main(){
	//freopen("input.txt", "rt", stdin);
	int i, A[10], B[10], as=0, bs=0, lw=0;
	for(i=0; i<10; i++){
		scanf("%d", &A[i]);
	}
	for(i=0; i<10; i++){
		scanf("%d", &B[i]);
	}
	for(i=0; i<10; i++){
		if(A[i]>B[i]){
			as=as+3;
			lw=1;
		}
		else if(A[i]<B[i]){
			bs=bs+3;
			lw=2;
		}
		else{
			as+=1;
			bs+=1;
		}
	}
    
	printf("%d %d\n", as, bs);
    
	if(as==bs){
		if(lw==0) printf("D\n");
		else if(lw==1) printf("A\n");
		else printf("B\n");
	}
	else if(as>bs) printf("A\n");
	else printf("B\n");			
	return 0;
}

  사이트의 답과 비슷한 논리인 것을 확인했다. 

    20번 문제   

    내가 풀이한 답   

  흔한 가위 바위 보 게임이였고 가위 1, 바위 2, 보 3이라고 했을 때, 1 < 2, 2 < 3, 3 <1 그리고 무승부 총 4가지 경우에서 무승부를 따로 처리하고 3과 1만 반대로 처리하였다.

 명심하자 char 변수에 대입할 수 있는 것이 "A"가 아니라 'A'여야 한다는 것을 

#include <stdio.h>

int a[101];
int b[101];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int n, i;
	char res;
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	
	for(i=0; i<n; i++){
		scanf("%d", &b[i]);
	}
	
	for(i=0; i<n; i++){
		if((a[i] == 3 && b[i] == 1) || (a[i] == 1 && b[i] == 3)){
			res = a[i] < b[i] ? 'A' : 'B';
		} 
		else if(a[i] == b[i]) res = 'D';
		else {
			res = a[i] > b[i] ? 'A' : 'B';
		}
		printf("%c\n", res);
	}
	
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
int main(){
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
	int a[101], b[101], i, j, n, A=0, B=0;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	for(i=1; i<=n; i++){
		scanf("%d", &b[i]);
	}
	for(i=1; i<=n; i++){
		if(a[i]==b[i]) printf("D\n");
		else if(a[i]==1 && b[i]==3) printf("A\n");
		else if(a[i]==2 && b[i]==1) printf("A\n");
		else if(a[i]==3 && b[i]==2) printf("A\n");
		else printf("B\n");
	}
	return 0;
}

  사이트의 답은 A를 기준으로 생각을 하고 접근하였다. 따로 논리적으로 다를 것은 없었다.

    19번 문제   

    내가 풀이한 답   

  배열안에서 뒤에 나오는 숫자들과 비교해서 큰 숫자나 같은 숫자 존재하면 분노 유발자가 없다고 생각하였다. 

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

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int n, i, j, avenger = 0;
	bool flag;
	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++){
		flag = true;
		for(j=i+1; j<n; j++){
			if(arr[i] <= arr[j]){
				flag = false;
				break;
			}
		}
		if(flag) avenger++;
	}
	
	printf("%d", avenger);
    
    free(arr);
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

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

  사이트의 답은 거꾸로 생각해서 접근하였다. 뒤에서부터 차례로 비교해서 앞에 숫자와 비교해서 앞의 숫자가 크면 분노 유발자가 되는 것이다.

 거꾸로 접근하는 방법도 잊지 않았어야 했는데 앞으로는 명심해야겠다. 

#include <iostream>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int n, i, avenger = 0;
	cin >> n;
	int *arr = new int[n];
	
	for(i=0; i<n; i++){
		cin >> arr[i];
	}
	
	int max = arr[n-1];

	for(i=n-2; i>=0; i--){
		if(max < arr[i]){
			max = arr[i];
			avenger++;
		}
	}
	
	cout << avenger << endl;
	delete[] arr;
	
	return 0;
}

 오랜만에 C++로 다시 짜보았다.

 결과는 통과하였다.

    18번 문제   

    내가 풀이한 답   

  순회(for)를 돌면서 측정값(a)이 m값을 넘으면 alarm값을 증가시켜주고 거기다 max값보다 크면 max값도 갱신시켜준다. 그리고 m값 보다 작으면 alarm값을 0으로 초기화시켜준다.  

#include <stdio.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int n, m, i, a, max=-1, alarm = 0;
	
	scanf("%d", &n);
	scanf("%d", &m);
	
	for(i=0; i<n; i++){
		scanf("%d", &a);
		if(a>m) {
			alarm++;
			if(alarm > max) max = alarm;
		}
		else alarm = 0;
	}
	
	printf("%d", max);
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

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

  사이트의 답도 논리적으로 같았다.

    17번 문제   

    내가 풀이한 답   

  순회(for)를 돌아 n까지의 합을 구해서 입력된 값과 비교하였다. 

#include <stdio.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, i, j, num, res, sum;
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		sum = 0;
		scanf("%d", &num);
		scanf("%d", &res);
		
		for(j=1; j<=num; j++){
			sum += j;
		}
		
		if(res == sum) printf("%s\n", "YES");
		else printf("%s\n", "NO");
	}

	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
int main(){
	freopen("input.txt", "rt", stdin);
	int n, sum=0, i, j, m, ans;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d %d", &m, &ans);
		sum=0;
		for(j=1; j<=m; j++){
			sum+=j;
		}
		if(ans==sum) printf("YES\n");
		else printf("NO\n");
	}	
	return 0;
}

  사이트의 답도 똑같았다.

    조금 더 정리   

 뭔가 이대로 넘어가기엔 찜찜해서 좀 더 알아보았다. 어떤 블로그를 보니 시간복잡도 면에서 효과적인 방법을 찾았다. 원리는 다음과 같다. 10을 예로 들면 첫자리와 끝자리를 좁혀나가면서 더하면 11이 5번 나오는 것을 확인할 수 있다. 홀수인 11인 경우도 짝수 공식에 나머지 하나를 더해주면 된다.

#include <stdio.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, i, j, num, res, sum;
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		sum = 0;
		scanf("%d", &num);
		scanf("%d", &res);
		
		if(num%2==0) sum = (1+num) * (num/2);
		else sum = (1+num) * (num/2) + (num/2 + 1);
		
		if(res == sum) printf("%s\n", "YES");
		else printf("%s\n", "NO");
	}

	return 0;
}

 결과는 통과하였다.

    16번 문제   

    내가 풀이한 답   

  두 문자열에 해당하는 알파벳의 개수만 확인하면 되므로 하나의 배열에서 첫 번째 문자열은 +로 두 번째 문자열은 -로 0이 되지 않은 인덱스가 있으면 NO, 없으면 YES로 해결하려고 했었는데 순서가 문제였다. 그래서 방법을 바꾸어 생각해 정렬을 생각해보았다. 하지만, 정렬이 어떤식으로 나오는지 몰랐기 때문에 출력을 해봤더니 대문자가 먼저 나왔다. 예) AACabee

 이 점을 이용해서 순서대로 비교를해서 하나라도 다르면 NO, 모두 일치하면 YES를 출력하였다.  

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

char a[100];
char b[100];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	
	int i;
	bool flag = true; 
	
	scanf("%s", &a);
	scanf("%s", &b);
	
	sort(a, a + strlen(a));
	sort(b, b + strlen(b));
	
	for(i=0; i<strlen(a); i++){
		if(a[i] != b[i]) {
			flag = false;
			break;
		}
	}
	
	if(flag) printf("%s\n", "YES");
	else printf("%s\n", "NO");
	return 0;
}

 결과는 잘 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<algorithm>
int a[60], b[60];
int main(){
	freopen("input.txt", "rt", stdin);
	int n, i;
	char str[100];
	scanf("%s", &str);
	for(i=0; str[i]!='\0'; i++){
		if(str[i]>=65 && str[i]<=90)
			a[str[i]-64]++;
		else a[str[i]-70]++;
	}
	
	scanf("%s", &str);
	for(i=0; str[i]!='\0'; i++){
		if(str[i]>=65 && str[i]<=90)
			b[str[i]-64]++;
		else b[str[i]-70]++;
	}
	
	for(i=1; i<=52; i++){
		if(a[i]!=b[i]){
			printf("NO\n");
			exit(0);
		}
	}
	printf("YES\n");	
	return 0;
}

   여기서는 아스키 코드를 적극적으로 활용하였다. A~Z 까지는 65번~90번이고 a~z 까지는 97번~121번인 것을 말이다. (이제와서 생각해보니 맨 위 코드에서 정렬을 할 때 왜 대문자부터 나왔는지 이제 이해가 간다.) 그래서 대문자는 64를 빼고 소문자는 70을 빼서 1부터 52까지의 인덱스를 활용한 것이다. 

    15번 문제   

    내가 풀이한 답   

  마땅한 방법이 떠오르지 않아 일반적인 순회(for)를 두 번 돌아 모든 경우의 수를 다 접근하며 소수를 판별하는 식으로 작성하였다.  

#include <stdio.h>
using namespace std;

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

	int n, i, j, cnt = 0;
	bool flag;
	scanf("%d", &n);
	
	for(i=2; i<=n; i++){
		flag = true;
		for(j=2; j<i; j++){
			if(i%j==0){
				flag = false;
				break;
			}
		}
		if(flag==true) cnt++;
	}
	
	printf("%d", cnt);
	return 0;
}

 결과는 예상대로 시간초과가 났다. 

 곰곰히 생각해봤지만 마땅한 답이 떠오르지 않아서 강의 도입부를 참조했다. 시간 초과가 나는 이유의 대부분은 굳이 참조하지 않아도 될 경우의 수를 모두 접근했을 때 발생한다는 얘기를 들었다. 소수 판별에서도 소수라고 판단이 되는 경우의 수를 제곱근으로 줄일 수 있다. 밑에 예시처럼 36을 보면 나머지가 0이되는 경우의 수는 총 10개이지만 5개만 확인해도 소수판별이 가능하다는 이야기이다.  

    사이트의 답안   

#include <stdio.h>
using namespace std;

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

	int n, i, j, cnt = 0;
	bool flag;
	scanf("%d", &n);
	
	for(i=2; i<=n; i++){
		flag = true;
		for(j=2; j*j<=i; j++){
			if(i%j==0){
				flag = false;
				break;
			}
		}
		if(flag==true) cnt++;
	}
	
	printf("%d", cnt);
	return 0;
}

12번째 줄 순회(for)문에서 제곱근(sqrt 함수) 대신 왼쪽에 j를 한번 더 곱해주었다. 그 결과 통과를 했다.

    조금 더 정리   

  소수 판별에 대해 좀 더 공부하고 싶어서 인터넷을 찾아보았다. 찾아보니 에라토스테네스의 체 라는 방법이 나왔다. 논리는 다음과 같다. 2부터 입력받은 수까지 for문을 돌며 각 소수의 배수들은 소수가 아니므로 다 제외시키는 방법이다. 

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

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

	int n, i, j, cnt=0;
	scanf("%d", &n);
	int *arr = (int *)malloc(sizeof(int) * n);
	memset(arr, 0, n * sizeof(int));
	
	for(i=2; i<=n; i++){
		if(arr[i]==1) continue;
		for(j = i+i; j<=n; j+=i) arr[j] = 1;
	}
	
	for(i=2; i<=n; i++){
		if(arr[i]!=1) cnt++;
	}
	
	printf("%d", cnt);
	free(arr);
	return 0;
}

    14번 문제   

    내가 풀이한 답   

  입력받은 수를 뒤집는 함수인 reverse 함수는 순회(while)를 돌면서 res 변수에 10씩 곱해주고 나머지를 더해주면 되었고 소수를 판별하는 isPrime 함수는 2부터 자기자신 전까지의 숫자를 순회(for)를 돌면서 나머지가 0이되는 숫자가 있으면 소수가 아니라고 판단하였다. 

#include <stdio.h>
using namespace std;

int reverse(int x){
	int num, res = 0;
	
	while(x>0){
		num = x%10;
		res = res * 10 + num;
		x /= 10;
	}
	
	return res;
}

bool isPrime(int x){
	bool flag = true;

	for(int i=2; i<x; i++){
		if(x%i==0) {
        		flag = false;
            		break;
        	}
	}
	
	return flag;
}

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

	int n, i, a, rev;
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		scanf("%d", &a);
		rev = reverse(a);
		if(isPrime(rev)){
			printf("%d\n", rev);
		}
	}
		
	return 0;
}

 그 결과 틀린 케이스가 2개가 발견되었다. 

 알고보니 10과 100의 뒤집은 숫자 1은 소수가 아니기 때문에 따로 1은 소수가 아니라는 작업을 해줬어야 했다. 조건문으로 따로 빼서 코드를 추가하였다.

#include <stdio.h>
using namespace std;

int reverse(int x){
	int num, res = 0;
	
	while(x>0){
		num = x%10;
		res = res * 10 + num;
		x /= 10;
	}
	
	return res;
}

bool isPrime(int x){
	bool flag = true;
	
	if(x==1) flag = false;
	
	for(int i=2; i<x; i++){
		if(x%i==0) {
        		flag = false;
            		break;
        	}
	}
	
	return flag;
}

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

	int n, i, a, rev;
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		scanf("%d", &a);
		rev = reverse(a);
		if(isPrime(rev)){
			printf("%d\n", rev);
		}
	}
		
	return 0;
}

그 결과 통과를 했다.

    사이트의 답안   

#include<stdio.h>

int reverse(int x){
	int res=0, tmp;
	while(x>0){
		tmp=x%10;
		res=res*10+tmp;
		x=x/10;
	}
	return res;
}

bool isPrime(int x){
	int i;
	if(x==1) return false;
	bool flag=true;
	for(i=2; i<x; i++){
		if(x%i==0){
			flag=false;
			break;
		}
	}
	return flag;
}
			
int main(){
	freopen("input.txt", "rt", stdin);
	int n, num, i, tmp;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &num);
		tmp=reverse(num);
		if(isPrime(tmp)) printf("%d ", tmp);
	}
	return 0;
}

  사이트의 답안과 내 코드는 논리적으로 똑같았다.

    13번 문제   

    내가 풀이한 답   

  문제를 보자마자 배열의 0~9 index를 이용해 값을 저장하고 최대값을 찾으려고 하였다. 주어진 입력 조건에 자연수의 길이는 100을 넘지 않는다고 되어 있는데 최대가 99이므로 long long 타입으로도 받을 수 없었다. char형 배열을 이용해서 각각을 정수로 바꿔주는 방법을 시도하였다. 

#include <stdio.h>
using namespace std;

char array[101];
int digit[11];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	
	int i, temp, max, index;
	scanf("%s", &array);
	
	for(i=0; array[i]!='\0'; i++){
		temp = array[i] - '0';
		digit[temp]++;
	}
	
	for(i=0; i<10; i++){
		if(digit[i]>=max) {
			max = digit[i];
			index = i;
		}
	}
	
	printf("%d", index);

	return 0;
}

그 결과 통과를 했다.

    사이트의 답안   

#include<stdio.h>
int ch[10];
int main(){
	//freopen("input.txt", "rt", stdin);
	int i, digit, max=-2147000000, res;
	char a[101];
	scanf("%s", &a);
	for(i=0; a[i]!='\0'; i++){
		digit=a[i]-48;
		ch[digit]++;
	}
	for(i=0; i<=9; i++){
		if(ch[i]>=max){
			max=ch[i];
			res=i;
		}
	}
	printf("%d\n", res);
	return 0;
}

  사이트의 답안과 내 코드는 논리적으로 똑같았다.

    12번 문제   

    내가 풀이한 답   

   11번 문제보다 입력 범위가 늘었다. 그래서 전 코드에서 분기문의 조건을 늘리는 작업을 했다.

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, cnt;
	scanf("%d", &n);
	
	if(n<10){
		cnt = n;
	} 
	else if(n>=10 && n<100){
		cnt = (n-9)*2 + 9;
	}
	else if(n>=100 && n<1000){
		cnt = (n-9-90)*3 + (90*2) + 9;
	}
	else if(n>=1000 && n<10000){
		cnt = (n-9-90-900)*4 + (900*3) + (90*2) + 9;
	}
	else if(n>=10000 && n<100000){
		cnt = (n-9-90-900-9000)*5 + (9000*4) + (900*3) + (90*2) + 9;
	}
	else if(n>=100000 && n<1000000){
		cnt = (n-9-90-900-9000-90000)*6 + (90000*5) + (9000*4) + (900*3) + 
		(90*2) + 9;
	}
	else if(n>=1000000 && n<10000000){
		cnt = (n-9-90-900-9000-90000-900000)*7 + (900000*6) + (90000*5) + (9000*4) + 
		(900*3) + (90*2) + 9;
	}
	else if(n>=10000000 && n<100000000){
		cnt = (n-9-90-900-9000-90000-900000-9000000)*8 + (9000000*7) + (900000*6) + 
		(90000*5) + (9000*4) + (900*3) + (90*2) + 9;
	}
	else if(n>=100000000 && n<1000000000){
		cnt = (n-9-90-900-9000-90000-900000-9000000-90000000)*9 + (90000000*8) + 
		(9000000*7) + (900000*6) + (90000*5) + (9000*4) + (900*3) + (90*2) + 9;
	}

	printf("%d", cnt);
	
	return 0;
}

그 결과 통과를 했지만 너무 효율성이 없다고 생각을 했다. 

그래서, 11번 문제의 코드를 그대로 다시 입력해봤더니 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, cnt, i, temp;
	scanf("%d", &n);
	
	for(i=1; i<=n; i++){
		temp = i;
		while(temp>0){
			temp /= 10;
			cnt++;
		}
	}

	printf("%d", cnt);
	
	return 0;
}

 결과는 범위가 10억까지 늘어서 그런지 Time Limit이 걸려서 통과하지 못했다.

 그래서 방법을 바꾸어 생각해보았다. 위에서 작성한 분기문을 순회(while)문을 사용해서 작성하였다. 각각의 자릿수에 해당하는 수의 개수는 9(1~9), 90(10~99), 900(100~999), 9000(1000~9999) .... 규칙적으로 10이 곱해져서 증가하는 것을 이용하였다. 

 입력받은 n의 자리수를 확인하기 위한 check 변수와 각 자리수의 숫자 개수를 확인하기 위해 임시로 사용한 temp 변수와 각 자리수를 나타내는 digit 변수를 사용해서 코드를 완성했다. 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	
	int n, cnt, check = 9, digit = 1, temp = 9;
	scanf("%d", &n);
	
	if(n>=1 && n<=9){
		printf("%d", n);
		return 0;
	}
	
	while(n >= check){
		cnt += (temp*digit);
		temp = temp * 10;
		check = temp + check;
		digit++;	
	}
	check = check / 10;
	cnt += (n - check) * digit;
	
	printf("%d", cnt);
	
	return 0;
}

 n이 137인 경우 흐름은 다음과 같다.

코드를 채점 시스템에 적용해보니 통과를 했다.

    사이트의 답안   

#include<stdio.h>
int main(){
	//freopen("input.txt", "rt", stdin);
	int n, sum=0, cnt=1, digit=9, res=0;
	scanf("%d", &n);
	while(sum+digit<n){	
		sum=sum+digit;
		res=res+(cnt*digit);
		cnt++;
		digit=digit*10;
	}
	res=res+((n-sum)*cnt);
	printf("%d\n", res);
	return 0;
}

  사이트의 답안은 마지막으로 작성한 코드와 논리적으로 똑같았다.