[알고리즘 문제풀이] 13. 가장 많이 사용된 자릿수★

 

#include <stdio.h>
int main(void){
   //freopen("input.txt", "rt", stdin);
   
   // 1. 자연수를 입력 받는다.
   char array[100];
   
   int n, cnt, result = 0; 
   int max = -2147000000;
   scanf("%s", &array);	
   
   for(int i = 0; array[i] != '\0'; i++){
   		cnt = 0;
	   	for(int j = 0; array[j] != '\0'; j++){
	   		if( array[j] == array[i]) cnt++;
		   }
		   
		cnt -= 1;
		if(cnt > max) {
			   	 
			   	 result = array[i] - 48;
			   	 
			   	 printf("i = %d \n", i);
			   	 printf("cnt는 %d \n", cnt);
			   	 printf("max는 %d \n", max);
			   	 printf("result는 %d \n", result);
			   	 
			   	 max = cnt;

			   }
		else if(cnt == max){
			   	if(result < (array[i] - 48)) result = array[i] - 48;
			   	printf("i = %d \n", i);
			   	 printf("cnt는 %d \n", cnt);
			   	 printf("max는 %d \n", max);
			   	 printf("result는 %d \n", result);
		   }
   }
   
   printf("%d\n", result);
}

 

예시를 넣고 돌렸더니 잘 나왔다.

코드가 문제에 맞게 잘 작동한다.

 

해설은 다르게 풀었다.

0부터 9까지 각 자릿수의 갯수를 넣은 배열 digit_cnt[10]을 추가하였고

첫번째 for 문은 같으나

두번쩨 for 문은 0~9까지만 진행하였다.

또  두 for 문이 독립적으로 실행되기 때문에 컴파일 시간이 n제곱에서 n+9로 단축되었다.

 

해답

#include <stdio.h>
int digit_cnt[10];

int main(void){
   //freopen("input.txt", "rt", stdin);
   // 1. 자연수를 입력 받는다.
   char array[100];
   int n, cnt, result, digit = 0; 
   int max = -2147000000;
   scanf("%s", &array);	
   
   // 2. digit_cnt[10]배열에 각 자릿수의 갯수를 넣는다. 
   for(int i = 0; array[i] != '\0'; i++){
   		digit =  array[i] - 48;
   		digit_cnt[digit]++;
		   }
	
	// 3. 자릿수의 갯수를 비교하여 결과를 출력한다.
	for(int i = 0; i <=9; i++){
		if(digit_cnt[i] >= max) {
			max = digit_cnt[i];
			result = i;
		}
	}
   
   printf("%d\n", result);
}

 

자릿수의 개수가 같은 경우,

i 와 기존 i 를 비교해야 하는데
i는 0부터 커지므로 당연히 최신 i 가 기존 i 보다 크다.
따라서 부등호  >= 같다를 추가하였다. 

// 3. 자릿수의 갯수를 비교하여 결과를 출력한다.
	for(int i = 0; i <=9; i++){
		if(digit_cnt[i] >= max) {
			max = digit_cnt[i];
			result = i;
		}
	}