백준(BAEKJOON): 단어 공부(1157번)

Source

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

입력

첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.

출력

첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.

예제 입력 1

Mississipi

예제 출력 1

?

예제 입력 2

zZa

예제 출력 2

Z

예제 입력 3

z

예제 출력 3

Z

예제 입력 4

baaa

예제 출력 4

A

해설

문제의 입력 조건과 처리, 출력 조건을 명세화해 보자.

1. 입력
   • 알파벳 대소문자로 이루어진 문자열
   • 문자열의 길이는 최대 1,000,000을 넘지 않음.
2. 처리
   • 물자열에서 각 알파벳의 출현 빈도를 계산한다.
   • 이때 대소문자 구분은 없다.
3. 출력
   • 최빈도의 문자를 출력한다.
   • 이때 최빈도 문자가 복수이면 "?"을 출력한다.

각 알파벳의 출현 빈도를 계산해야 하는데 이때 대소문자의 구분을 하지 않아야 한다. string.h을 선언했으니 이 헤더에 포함된 아래의 함수를 이용하여 문자열 input의 대문자 혹은 소문자로 바꿀 수 있을 것이다.

#include <string.h>

strlwr(문자열); //소문자로 바꾸기
strupr(문자열); //대문자로 바꾸기

아스키코드를 이용하여 직접 처리하는 코드를 아래와 같이 작성하였다. input[i]가 대문자인 경우에는 대문자의 아스키코드에서 65를 뺀다. 그 같(pos)을 알파벳 26자에 대응하는 alpha[0~25]의 첨자로 하여 해당 메모리에 1을 더한다. 이러한 방식으로 각 알파벳이 출현할 때마다 1을 더하여 그 출현 빈도를 누적한다. 만약 소문자인 경우에는 input[i]에서 97을 빼서 위와 동일하게 해당 알파벳의 출련 빈도를 누적한다.

    for (i = 0; i < len; ++i) {
        if ( input[i] < 91){
            pos = input[i] - 65;
            alpha[pos] += 1;
        } else {
            pos = input[i] - 97;
            alpha[pos] += 1;
        }

이제 처리된 결과를 이용하여 적절하게 출력 코드를 완성하면 된다. 우선 최빈도를 보이는 문자를 찾아야 한다.

    for (i = 0; i < 26; ++i) {
        if (alpha[i] > max) {
            max = alpha[i];
            pos = i;
        }
    }

빈도수가 저장된 배열인 alpha[]의 각 원소의 값을 서로 비교하여 가장 큰 수를 찾아낸 후 그 값을 max에 저장한다. 이때 해당 배열의 첨자까지 저장해 두어야만 나중에 최빈도를 보이는 문자를 출력할 수 있으므로 pos에 최빈도값을 갖는 배열 첨자도 저장해 둔다. 다음으로 복수의 문자가 최빈도를 보이는 경우에는 ?를 출력해야 한다는 조건을 처리해야 한다.

    for (i = 0; i < 26; ++i) {
        if (alpha[i] == max) {
            dFlag += 1;
        }
    }

앞선 코드에서 최빈도 max를 알아냈으므로 배열 alpha[]에서 max와 동일한 값을 갖는 경우가 나타날 때마다 dFlag에 1을 누적한다. dFlag가 2 이상인 경우에는 복수의 문자에서 최빈값이 나왔다는 의미가 되다. 자 이 dFlag의 값을 이용하여 ?을 출력하는 경우 최빈도를 보이는 알파벳을 출력하는 코드 아래와 같이 작성한다.

    if (dFlag != 1) {
        printf("?\n");    
    } else {
        alphaFlag = pos + 65;
        printf("%c\n", alphaFlag);
    }

dFlag를 확인하여 그 값이 1이 아닌 경우는 ?을 출력하고 1인 경우에는 앞서 저장해둔 pos에 65를 더해서 alphaFlag에 저장한다. 이를 통해 alphaFlag에는 대문자의 아스키코드에 대응하는 정수값이 저장된다. 이 정수를 printf() 함수에서 문자 서석으로 출력하게 되면 해당 정수에 대응하는 문자를 출력한다.
지금까지의 과정을 전체 코드로 완성하면 아래와 같다.

소스코드: c

#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[])
{
    char input[1000000];
    int alpha[26] = {[0 ... 25] = 0};
    int i, len, pos, dFlag = 0, alphaFlag= 0, max = 0;  


    scanf("%s", input);
    len = strlen(input);
    for (i = 0; i < len; ++i) {
        if ( input[i] < 91){
            pos = input[i] - 65;
            alpha[pos] += 1;
        } else {
            pos = input[i] - 97;
            alpha[pos] += 1;
        }
    }

    for (i = 0; i < 26; ++i) {
        if (alpha[i] > max) {
            max = alpha[i];
            pos = i;
        }
    }

    for (i = 0; i < 26; ++i) {
        if (alpha[i] == max) {
            dFlag += 1;
        }
    }

    if (dFlag != 1) {
        printf("?\n");    
    } else {
        alphaFlag = pos + 65;
        printf("%c\n", alphaFlag);
    }
    return 0;
}