백준 1157번: 단어공부

문제

[BOJ[C++] 백준 1157번: 단어공부

문제는 https://www.acmicpc.net/problem/1157를 클릭해서 볼 수 있다.

풀이

아스키 코드를 이용하여 문자의 개수를 세는 문제였다. character_count[26] 배열을 만들어 단어에서 'A'부터 'Z'까지 각 문자가 몇 번 나왔는 지 개수를 저장했다. 문자는 index가 0이면 'A', index가 25이면 'Z' 이런 식으로 구분했다.

먼저 소문자와 대문자의 구분을 없앴다. 단어의 길이만큼 반복문을 돌면서 소문자인 경우 아스키 코드값 차이만큼 빼 대문자로 바꾸어 주었다. (소문자는 대문자보다 아스키 코드값이 각각 32 만큼 크다.) 그런 다음 character_count 배열에서 개수를 1씩 더해줬다.

다음은 가장 많이 사용된 문자를 찾았다. character_count를 돌면서 max_count보다 크면 max_count 값을 현재 개수로 갱신해주고, max_used_character에 현재 문자를 저장해줬다.

가장 많이 사용된 문자의 개수는 max_count와 같은 개수를 가지는 다른 문자가 있는 지 확인해서 구했다. 다른 문자가 있으면 ? 없으면 max_used_character를 출력해 답안을 완성했다.

공부

첫 제출에서 시간 초과가 나왔다. 문제를 풀 때 시간 제한이 2초이고 주어진 단어의 길이가 1,000,000을 넘지 않기 때문에 시간이 충분하다고 생각했다. 시간 초과가 날 만한 코드를 찾다가 for문 코드를 살펴보게 되었다. 예상대로 시간 초과의 범인은 get_character_count() 함수의 for문이었다.

for문 안 조건식에 i < strlen(word) 를 넣으면 조건을 확인할 때 마다 strlen 함수가 실행된다. strlen는 문자열에서 NULL 이 들어올 때까지 문자열을 하나씩 읽는다. 문자열의 길이가 n일 때 for문의 시간 복잡도는 O(n^2) 가 된다. 따라서 시간 초과를 피하기 위해 for문 밖에서 length_of_word = strlen(word) 처럼 한 번만 실행되도록 바꿔주거나 word[i] ! = '\0' 으로 NULL이 들어오기 전까지로 조건식을 바꿔주어야 한다.

호호님의 코드를 보면서 가장 많이 사용된 문자의 개수를 더 쉽게 구하는 방법에 대해 알게 됐다. 필자는 가장 많이 사용된 문자를 구한 뒤 다시 반복문을 돌면서 개수를 구했다. 호호님은 가장 많이 사용된 문자를 구할 때 max_count랑 현재 개수가 같으면 지금까지 구한 max_used_character는 적어도 2개 이상이라는 뜻이므로 -1로 표시해주셨다. 이렇게 하면 max_count는 그대로 살릴 수 있으면서 가장 많이 사용된 문자가 몇 개인지 까지 한번에 구할 수 있다.

// 호호님 코드
else if (current_count == max_count && current_character != 0)
			// 가장 많이 사용된 알파벳이 2개 이상이라는 뜻이다.
			max_used_character = -1;

// 필자의 코드
int check_number_of_most_used_character() {
	for (i = 0; i < 26; i++) {
		if (character_count[i] == max_count && i + 65 != max_used_character)
			return 1;	// 2개 이상 존재
	}

	return 0;			// 한 개만 존재
}

코드

정답 코드 1

#include <stdio.h>
#include <string.h>

char word[1000001] = "";				// 알파벳 대소문자로 이루어진 단어
int character_count[26] = {0};				// 사용된 알파벳의 개수
int i = 0;
int current_character;
int max_used_character, max_count;

void get_character_count();
void find_most_used_character();
int check_number_of_most_used_character();

int main() {

	scanf("%s", word);

	get_character_count();
	find_most_used_character();

	if (check_number_of_most_used_character() == 0)
		printf("%c\n", max_used_character);
	else
		printf("?\n");

	return 0;
}

void get_character_count() {
	for (i = 0; word[i] != '\0'; i++) {
		current_character = word[i];

		// 소문자일 경우 대문자로 변환한다.
		if (current_character >= 'a')
			current_character -= 32;

		character_count[current_character - 65]++;
	}
}

void find_most_used_character() {
	for (i = 0; i < 26; i++) {
		int current_count = character_count[i];

		if (current_count > max_count) {
			max_count = current_count;
			max_used_character = i + 65;
		}
		else if (current_count == max_count)
			max_used_character = -1;
	}
}

int check_number_of_most_used_character() {
	for (i =0; i < 26; i++) {
		if (character_count[i] == max_count && i + 65 != max_used_character)
			return 1;	// 2개 이상 존재
	}

	return 0;			// 한 개만 존재
}

정답 코드 2

#include <stdio.h>
#include <string.h>

char word[1000001] = "";					// 알파벳 대소문자로 이루어진 단어
int character_count[26] = {0};					// 사용된 알파벳의 개수
int i = 0;
int current_character;
int max_used_character, max_count;

void get_character_count();
void find_most_used_character();

int main() {

	scanf("%s", word);

	get_character_count();
	find_most_used_character();

	if (max_used_character != -1)
		printf("%c\n", max_used_character);
	else
		printf("?\n");

	return 0;
}

void get_character_count() {
	for (i = 0; word[i] != '\0'; i++) {
		current_character = word[i];

		// 소문자일 경우 대문자로 변환한다.
		if (current_character >= 'a')
			current_character -= 32;

		character_count[current_character - 65]++;
	}
}

void find_most_used_character() {
	for (i = 0; i < 26; i++) {
		int current_count = character_count[i];

		if (current_count > max_count) {
			max_count = current_count;
			max_used_character = i + 65;
		}
		else if (current_count == max_count && current_character != 0)
			// 가장 많이 사용된 알파벳이 2개 이상이라는 뜻이다.
			max_used_character = -1;
	}
}

채점 결과