[TIL]2022/02/22

1. 백준 1157 단어 공부

 

가장 많이 고민한 부분

입력을 어떻게 받을 것인가? - 입력 받는 문장이 몇 글자인지 안알려준다. 처음에는 sentence[1000000]처럼 문자열을 통채로 받고, 반복문을 통해서 가장 많이 존재하는 문자를 찾으려고 했었다. 조건에서 최대 크기가 1,000,000라고 하지만 sentence[1000000]라고 메모리를 잡으면 틀렸다고 한다. 아마도 무식하게 많이 잡아서 그런듯. 그래서 고민하다가 애초애 문제를 해결하는데 필요한 데이터는 문자의 개수였고, 문자열 전체를 배열에 저장할 필요가 없다는 것을 깨달았다. 그래서 문자 하나하나를 받아서 해당 문자의 개수를  +1 하는 전략으로 수정했다. 이렇게 하면 문장의 글자수에 구애받지 않을 수 있다(한 문자 단위로 입력을 받으니까).

 

#include <stdio.h>
#include <ctype.h>
int main()
{
    
    int alpha[26]; char c; int max = 0; int max_index = 0; int dup = 0;
    for(int i = 0; i < 26; i++){
        alpha[i] = 0;
    }
    while(1){
        scanf("%c", &c);
        if(c == '\n'){
            break;
        }
            
        c = toupper(c);
        alpha[c - 65]++;
        
    }
    
    
    for(int i = 0; i < 26; i++){
            if(alpha[i] > max){
                max = alpha[i];
                max_index = i;
                dup = 0;
            }
            else if(alpha[i] == max){
                dup = 1;
            }
        }
 
    if (dup == 1)
        printf("%c", '?');
    else
        printf("%c", max_index + 65);
    
    return 0;
}

 

 

 

코드 해설

 

변수

alpha는 A-Z 문자의 빈도수를 저장하는 배열이다. 크기는 26이고 인덱스 0-25 순서대로 A-Z의 개수를 저장한다. 

max는 문장에서 가장 많은 문자 빈도 수. 

max_index는 가장 많은 빈도를 가진 문자의 alpha 배열 상 index. 예를 들어 주어진 문장에서 A가 가장 많으면 max_index는 0이다.

dup는 가장 많은 빈도 수를 가진 문자가 두 개 이상이면 1로 설정되어 여러 개의 단어가 최대 빈도를 지님을 알려줌.

 

우선은 alpha 배열을 초기화한다. 처음 코드를 작성했을 때 0으로 초기화를 빼먹어서 alpha가 쓰레기 값으로 채워져서 제대로 된 결과가 안나왔다. 왜 제대로 된 결과가 안나오냐면 초기화를 안했을 때 alpha에 들어간 쓰레기 값이 max 보다 큰 경우 제대로 된 비교가 안되기 때문! 

 

while로 단어 하나하나를 입력 받고 c에 저장. c가 단어의 끝(\n)일 때 반복문은 종료.

입력 받은 c가 소문자일 수도 있으니 대문자로 바꾸는 toupper()함수 사용.

ASCII 기준으로 대문자 A는 65다. c - 65 연산을 A는 0, B는 1 로 나와 해당 단어의 alpha 인덱스를 얻을 수 있다.

++연산을 통해 해당 단어의 빈도수를 +1 시킨다.

 

while이 종료돼 입력을 다 받으면, alpha 배열을 iterate하면서 가장 빈도가 많은 단어를 찾는다.

alpha[i] > max 로 가장 많은 빈도수를 새로 찾으면 업데이트 하고 dup를 0으로 설정한다(새로운 max를 찾았으니 가장 빈도가 많은 단어는 한 개다). 
alpha[i] == max로 최대 빈도수가 같은 다른 단어를 찾으면 dup를 1로 설정한다. 

출력은 dup가 1이면 ?로 하고 dup가 0이면 max_index의 값에 65를 더한 값을 char 형식으로 출력한다. 0 + 65는 A, 1 + 65는 B 등등이기에.

 

더 공부해야 할 것

 

getc, getchar 함수. 

문자열 입력 버퍼.