[백준 BOJ] 1157번 단어 공부 (C언어)

문제 설명

https://www.acmicpc.net/problem/1157

1157번: 단어 공부

 

접근 방법 - 아스키코드 이용한 문자열 연산 문제

백준의 1157번 문제는 전형적인 아스키코드 문제이다. 다만 난이도가 그렇게 낮은 문제는 아닌 듯해 보인다.

(문제 풀기에 앞서 아스키코드 값으로 A는 65, a는 97이란 걸 알아두자.)

필자는 해당 문제를 해결할 때, 각 26개의 알파벳 발생 빈도수를 따로 저장하는 배열을 별도로 선언하였다.

그리고 아래의 순서대로 코딩을 작성하였다.

아스키코드에 익숙하지 않다면 아래의 코드와 코드 설명을 꼭 같이 보길 바란다.

(설명과 (ex)를 같이 적어서 설명해보았는데, 되도록 (ex) 위주로 보는 게 이해가 조금은 더 빠를 듯하다.)

 

코드의 실행 순서

1) 문자열의 문자를 하나씩 입력받는 대로 알파벳 발생 빈도수 계산하기

(여기서 알파벳 발생 빈도수를 저장하는 배열을 count라 지정한다.)

입력받은 문자가 대문자라면, 해당 입력값에 'A'(65)을 뺀 count의 배열 번호에 1을 추가한다.

입력받은 문자가 소문자라면, 해당 입력값에 'a'(97)을 뺀 count의 배열 번호에 1을 추가한다.

(ex) 'A'를 입력받았다면, count ['A'-'A']++ => count [0]에 1을 추가

(ex) 'c'를 입력받았다면, count ['c'-'a']++ => count [2]에 1을 추가

 

2) 알파벳 최대 빈도수를 저장하는 변수로 max를 0으로 초기화하고 선언하기

동시에 많이 발생하는 알파벳을 저장하기 위해 문자형 변수인 c를 선언하기

 

3) count 변수의 값들을 탐색하며 최댓값인 max의 값을 결정하고, 이와 동시에 많이 발생한 알파벳도 함께 c에 저장하기

(ex) count 배열에서 배열 번호가 2인 배열 값이 가장 많을 때 => max=count [2], c=2+'A'='C'

 

4) 발생 빈도가 공동 1위인 알파벳이 있는지 판별하기 위해, 별도로 cnt를 0으로 초기화하면서 선언하기

배열 값을 탐색하며, 배열 값이 알파벳 최대 발생 빈도수와 동일할 때마다 cnt에 1을 추가하기

 

5) cnt가 1이면 최댓값을 가지는 알파벳이 하나로 유일하다는 것, 많이 발생한 알파벳인 변수 c의 값을 그대로 출력한다.

cnt가 2 이상이라면, 공동 1위인 알파벳이 있다는 것 => "?"를 출력한다.

 

6) 실행 종료한다.

 

후기 및 주의할 점 (시간 초과)

원리만 파악하면 어려운 문제는 아니지만 해결에 있어선 또 번거로운 문제였던 것 같다.

특히나 아스키코드가 아직 어색하다면 특히나 더 어려운 문제가 아니었을까...

실제로 필자가 대학교 후배 수업에 들어가서 실습 조교로 활동할 때 이 원리를 어떻게 설명하는 게 좋을지 난감했었다.

 

여담으로, 문자열 길이 범위가 비양심적이라 더 난감하다. 무려 문자열 최대 길이가 백만...

실제로 입력받는 과정과 알파벳 빈도수 측정 연산을 따로 작성하였다가 시간 초과가 났었다.

입력받는 것과 빈도수 측정을 동시에 하고 나니 시간 초과에서 벗어날 수 있었다.

혹시나 이 문제를 해결할 때 시간 초과로 애쓰고 있다면 이 점을 참고해보길 바란다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>
#include <string.h>

//백준 1157번 코드
char ch[1000000];
int count[26];
int main() {
	for (int i = 0; scanf("%c", &ch[i])!=EOF; i++) {
		if (ch[i] >= 'A' && ch[i] <= 'Z') {
			count[ch[i] - 'A']++;
		}
		else {
			count[ch[i] - 'a']++;
		}
	}

	int max = 0;	char c;
	for (int i = 0; i < 26; i++) {
		if (max < count[i]) { max = count[i];	c = i + 'A'; }
	}
	int cnt = 0;
	for (int i = 0; i < 26; i++) {
		if (max == count[i]) { cnt++; }
	}
	
	if (cnt == 1) { printf("%c", c); }
	else { printf("?"); }
}

 

제출 결과

(2021.12.19 백준 1157번 제출 결과)

(시간 초과는 언제 봐도 극혐)