[백준] 1157번: 단어공부

문제 주소 : www.acmicpc.net/problem/1157

1157번: 단어 공부

문제 확인

 

간단한 헤싱 문제

베열 인덱스 연산 대신 char 값을 그대로 인덱스로 사용해서 연산 횟수를 줄입니다.

 

풀이

 

fread를 통해 문자열을 한 번에 받아서 연산합니다. getchar을 통해 문자를 하나하나 입력받으면 보통 8ms~12ms가 나오게 됩니다.

문자를 입력받으면 그 문자의 아스키 값을 그대로 배열 인덱스로 사용하여 횟수를 체크합니다.

문자열 입력이 끝나면 최대 빈도수의 문자를 찾으며 같은 횟수의 문자가 나오면 dup 변수를 통해 문제 조건을 맞춥니다.

dup 변수가 1이라면 ?을 출력하고 아니라면 최대 빈도수 문자를 출력합니다.

 

코드

#include <cstdio>
 
int main() {
    char str[1000001];
    register int i, dif = 'a' - 'A';//대문자와 소문자 인덱스 차이
    int c[123] = {};
    fread(str, 1, sizeof(str), stdin);//한번에 입력받음
    for (char *p = str; *p; p++)
        ++c[*p];
    char m = 0, dup = 0;
    for (i = 'A'; i <= 'Z'; i++) {
        c[i] += c[i + dif];//빈도수를 합침
        if (c[i] > c[m]) {//최대 빈도수 문자 초기화
            m = i;
            dup = 0;//중복 초기화
        }
        else if (c[i] == c[m])//같으면 중복 설정
            dup = 1;
    }
    if (dup)
        putchar('?');
    else
        putchar(m);
}