[백준/C언어] 1157번 - 단어 공부

백준 웹사이트 "1157번 - 단어 공부" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1157번: 단어 공부

---

소스 코드

#include <stdio.h>
#include <string.h>
#include <ctype.h> //toupper() 사용

int main(void){
    char word[1000001]; //null 문자 저장을 위해
    scanf("%s", word);

    int alphabet[26];
    for(int i=0; i<26; i++){
        alphabet[i]=0;
    }

    int len = strlen(word); //for문에 넣으면 시간 초과
    for(int j=0; j<len; j++){
        char cur = toupper(word[j]);  //모든 알파벳을 대문자로 변환
        alphabet[cur-'A']++;
    }

    int max = 0, num = 0, max_alphabet = 0; //각각 초기화 필요
    for(int k=0; k<26; k++){
        if(alphabet[k] > max){
            max = alphabet[k];
            num = 1;
            max_alphabet='A'+k;
        }
        else if(max!=0 && alphabet[k] == max){
            num++;
        }
        else{
            continue;
        }
    }
    //printf("%d %d %d\n", max, num, max_alphabet);

    if(num==1){
        printf("%c\n", max_alphabet); // implicit type conversion
    }
    else{
        printf("?");
    }
}

---

문제 풀이

  가장 먼저 하는 것은 알파벳 대소문자로 이루어진 단어를 입력받는 것입니다. 이때 생성하는 char 배열의 길이는 1,000,001로 해야하는데, 입력의 마지막에 null 문자 저장을 위해 최대 크기보다 1만큼 크게 배열을 선언해줍니다.

  Line 14 ~ 18에서는 입력 단어의 각 알파벳을 대문자로 변환하고, 각 알파벳의 수를 구합니다. 이 부분에서 저는 처음에 Line 14을 작성하지 않고, Line 15을 for(int j=0; j<strlen(word); j++){ 과 같이 작성했습니다. 하지만 이로 인해 '시간 초과' 오류를 받았습니다. 백준 질의응답에 의하면, 그 이유는 for문의 조건 부분에 작성된 'strlen' 함수이었습니다. 'strlen' 함수는 입력 단어의 길이를 반환하는 함수이므로 단어의 길이에 비례하는 만큼의 시간을 소요합니다. 만약 이 함수를 for문의 조건문에 넣으면 for문이 반복될 때마다 시행되기 때문에, 결과적으로 (단어 길이)^2 만큼의 시간이 걸립니다. 이 문제처럼 입력 단어의 길이가 매우 긴 경우, 걸리는 시간은 제곱 배로 길어지기 때문에 시간 초과 오류가 납니다. 따라서 strlen 함수는 for문의 밖에서, 딱 한 번만 시행되도록 합니다.

  Line 16에서는 'toupper' 함수가 이용되는데, 소문자의 알파벳이 입력되면 그 알파벳의 대문자가 반환됩니다. 대문자가 입력되었을 경우에는 변환없이, 그대로 대문자가 반환됩니다. 대문자 알파벳을 크기 26의 'alphabet' 배열에 기록하여, 각 알파벳이 몇 번씩 등장하는지 기록합니다.

  여기까지 완료되면, alphabet[0]에는 단어에 'A'가 등장하는 횟수, alphabet[1]에는 'B'가 등장하는 횟수 등등이 저장됩니다. 이제는 이를 토대로 가장 많이 등장하는 알파벳을 구하고, 유일한지에 대한 여부를 판별해야 합니다. 이는 Line 20 ~ 33에서 진행하는데, 'max'는 최대로 등장하는 알파벳의 등장 횟수, 'num'은 가장 많이 사용된 알파벳의 개수, 'max_alphabet'은 가장 많이 사용된 알파벳을 의미합니다. 이때, 반드시 모두 초기화해야함을 잊지 말아주세요! 초기화시키지 않아도 예제 입력/출력은 모두 통과하지만, 실제 제출에서는 컴파일 오류가 뜰 수 있습니다 (제가 그랬습니다..ㅠㅠ). 여하튼 세 변수를 초기화시킨 후, for문을 돌리면 셋의 값을 얻게 됩니다. 제대로 구해지는지 확인하고 싶다면, Line 34과 같이 출력을 시켜보는 것도 좋지만, 제출할 때는 꼭 삭제하거나 주석 처리 해야합니다.

  마지막으로, num이 1일 경우에만 max_alphabet의 출력이 이루어지도록 합니다. num이 1보다 크다면, 최대로 등장하는 알파벳이 두 개 이상이기에 '?'를 출력해야 합니다. Line 37에서 max_alphabet은 int(정수)이지만, 출력을 "%c"로 하면 암시적 자료형변환 (implicit type conversion)이 일어나며 아스키 코드에 의해 해당하는 알파벳으로 출력됩니다.