[Baekjoon] 1620번: 나는야 포켓몬 마스터 이다솜

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

1620번: 나는야 포켓몬 마스터 이다솜

 

키미노 나마에와?

 

고작 방금 받은 피카추로 꼬렛을 잡자마자 바로 사천왕의 자리를 넘보는 다솜짱(폼 미쳤다).

 

우리 같은 일반인들은 몇날 며칠을 노가다해서 푸키먼을 키우고 나서야 겨우 도달할 수 있는 사천왕이 있는 장소에 고작 방금 잡은 꼬렛 한 마리 가지고 1 분도 안돼서 턱밑까지 다가갔다 온 다솜짱은 정말 놀랍게도 푸키먼 번호와 이름은 잘 못 외우는지, 우리의 도움이 필요한 상황이다.

 

---

 

문제 해결 과정

착안

도감(문자열 집합)에 등록되는 포켓몬의 이름(문자열)의 수가 많아질수록, 단순 문자열 비교를 통해 탐색하는 시간이 길어지므로 해시 알고리즘을 이용해, 최악의 경우에도 해시 코드가 같은(해시 충돌) 문자열끼리만 빠르게 비교할 수 있도록 해시 알고리즘을 활용하여 탐색을 구현하고자 하였다. 또한, 주어진 문제에서 입력되는 값이 숫자와 문자의 두 가지의 경우가 존재하므로 주어진 문제를 아래와 같이 단계적으로 나누어 생각하고 해결해보았다.

 

• 문제 해결을 위해 데이터를 저장할 컨테이너 선택.
• 주어진 \(N\) 개의 포켓몬 이름을 해시 알고리즘을 통해 해시 코드로 변환(해시 함수 구현), 해시 테이블 구현.
• 주어지는 \(M\) 회의 입력에서, 입력되는 값이 숫자(포켓몬 번호)인지 문자열(포켓몬 이름)인지에 따른 동작 수행.

 

단계적으로 코드를 작성하여 의도한 바에 맞게 정상적으로 작동하는지 간단하게 테스트 입출력을 통해 확인해 본 다음, 각각의 코드 블럭을 합쳐서(PPAP) 주어진 문제를 해결하고자 하였다.

 

출처: 피코타로(ピコ太郎, 본명: 고사카 다이마오(古坂 大魔王)) 유투브, 왠지 모르겠지만 짱구네 원장님이 생각난다...

 

구현

1) 문제에서 사용할 컨테이너 선택

오늘의 코딩 문제와 비슷한, 해시 알고리즘을 이용한 문자열과 문자열 집합 사이의 비교 문제를 다룬 이전 포스트에서는 STL map 클래스를 활용해 key의 값이 해시 코드, 그에 해당하는 요소를 문자열(정확히는, 해시 코드가 같은 문자열들을 요소로 가지는 STL vector 클래스)이 되도록 해시 테이블을 만들어 문제를 해결했었다.

 

이 문제에서 조금 다른 점으로는 번호가 주어졌을 때 이름을 출력하고, 반대로 이름이 주어졌을 때는 번호를 출력한다는 조건이다. 번호가 주어졌을 때 이름을 바로 출력하는 방법으로는 인덱스를 통해 접근이 쉬운 배열을 이용하는 것이 유리할 것이라고 생각했다. 그런데 이때 해시 테이블에서도 특정 key에 해당하는 요소를 문자열로 가지게 되면 똑같은 문자열 데이터를 두 개의 컨테이너가 가지게 되므로 이게 맘에 들지 않아서, 포켓몬 이름을 번호 순으로 저장할 배열을 우선 만든 뒤 해시 테이블에서는 key에 대응시킬 요소를 포켓몬 번호(에 대한 vector 클래스, 해시 충돌 해결 목적)로 지정하고자 했다.

 

* 문제에서 문자열을 다룰 때 string 클래스가 아닌 char* 를 사용해보았는데, 반복문과 관련한 char 배열을 사용할 때의 이슈가 있어서 문자열 데이터를 감싸는(래핑, wrapping)하는 구조체 Pokemon을 선언하여 사용했다(관련 내용은 별도로 포스팅 하였음). 동적 할당으로 char 배열을 선언해도 되는데 일일이 delete 하는 것이 번거롭다고 생각했다.

* 데이터 구조 측면에 중점을 두면, 포켓몬 번호 역시 Pokemon 구조체 안에 포함하는 게 논리적이기는 하지만 배열 인덱스로 번호를 나타내기만 해도 문제 해결에는 큰 지장이 없어서 굳이 번호까지 구조체의 멤버로써 저장하지는 않았다.

 

 

2) 해시 알고리즘

이전 포스트에서 사용했던 알고리즘인 다항 롤링 해시(polynomial rolling hash) 알고리즘(또는 라빈-카프 Rabin-Karp algorithm)의 코드를 다시 그대로(...) 활용해 문자열을 인수로 하여 해시 코드를 반환하는 함수를 구현하고 이용하고자 하였다(알고리즘의 간략한 설명은 이전 포스트 참고, 자세한 내용은 Wikipedia 사이트(영문)를 참고).

 

 

3) 입력 처리

도감 입력을 마친 다음에 제공되는 문자열 입력에 대하여, 주어지는 문자열이 포켓몬 번호(숫자)인지, 포켓몬 이름(알파벳으로 이루어진 문자열)인지를 확인하기 위해서 입력된 문자열의 가장 첫 번째 문자(0번 인덱스)의 ASCII Code가 문자 '9' 보다 같거나 작은지를 비교하여 포켓몬 번호인지 이름인지를 구별하고자 하였다. 문제에서 주어진 조건에 의해 숫자 또는 알파벳으로만 입력이 이루어지기 때문에 별도의 예외 조건은 굳이 작성하지 않았다.

* 내용 추가(2023-05-10): 항상 도감에 존재하는 이름만 쿼리로 들어온다는 문제의 전제 조건에 따라, 실행 속도 향상을 위해 해시 테이블에서 쿼리 문자열에 대한 해시 코드 값이 존재하는지 탐색하는 코드 부분(find)을 제외하였음.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <cstring>
#include <vector>
#include <map>

#define PRIME 53;
#define MODULO 4565710823;	// large prime number

using namespace std;

struct Pokemon
{
	char Name[21];
};

// polynomial rolling hash
size_t HashFunction(char str[21])
{
	size_t hash = 0;
	size_t power = 1;
	for (int i = 0; i < 21; i++)
	{
		if (!str[i]) break;

		hash += power * (str[i] - 'a' + 1);
		power *= PRIME;
	}

	return hash % MODULO;
}

int main()
{
	int N, M, Num = 1;
	scanf("%d %d", &N, &M);

	vector<Pokemon> Pokemons(N);
	map<size_t, vector<int>> HashTable;

	while (N--)
	{
		Pokemon pokemon;
		scanf("%s", pokemon.Name);
		Pokemons[Num - 1] = pokemon;

		size_t hash = HashFunction(pokemon.Name);
		HashTable.try_emplace(hash, vector<int>());
		HashTable.at(hash).push_back(Num++);
	}

	while (M--)
	{
		char query[21] = { 0, };
		scanf("%s", query);

		if (query[0] <= '9')
			printf("%s\n", Pokemons[atoi(query) - 1].Name);
		else
		{
			size_t hash = HashFunction(query);
			for (int num : HashTable[hash])
			{
				if (!strcmp(query, Pokemons[num - 1].Name))
				{
					printf("%d\n", num);
					break;
				}
			}
		}
	}

	return 0;
}

 

실행 결과

* 최초 코드 제출하여 문제 해결 이후, 일부 코드 수정(포스트에 반영하였음).