[Baekjoon] 14425번: 문자열 집합

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

14425번: 문자열 집합

 

오늘의 코딩 문제 풀이 포스팅부터는 본인의 공부 차원에서, 단순히 문제를 해결하기 위한 정답 코스만이 아니라 문제를 해결하면서 실패한 과정까지도 포스팅에 어느정도 간단히 기록을 해보려고 한다. 실패 과정을 복기하고, 왜 실패했는지 분석하는 방법은 단순히 공부 뿐 아니라 하물며 게임 실력 기르는 데에도 좋은 습관이다(게임을 그냥 즐기는 거 이상으로 잘 하고 싶다면... 리그 오브 레전드도 리플레이를 분석해 본인의 안 좋은 습관을 파악해서 고치고 상대방의 잘한 점을 분석해서 배워야 티어가 급상승 한다더라). 그래서 혹시나 블로그에 방문해서 풀이 과정을 같이 읽어주시는 초보 프로그래머 꿈나무들이 있다면 문제 해결 실패 과정을 같이 공유해서 실력을 향상하는 데에 도움이 되었으면 좋겠다.

 

---

 

문제 해결 과정

착안

주어진 \(N\) 개의 문자열 집합 내에서, query로 주어지는 \(M\) 개의 문자열과 정확히 같은 문자열이 몇 개나 존재하는지 탐색하는 것을 목표로 하는 문제이다. \(M\) 개의 문자열에 대해 각각 \(N\) 번 비교하는 가장 단순한 문자열 비교 알고리즘을 사용하면 \(10,000 × 10,000 = 100,000,000\) 회라는 무지막지한 횟수의 반복문을 실행해야하므로, 이는 너무 불필요하게 많은 계산을 필요로 한다. 따라서, 제한된 시간 내에 \(M\) 개의 문자열을 문자열 집합 내의 문자열과, 가능한 한 적은 횟수로 비교를 해서 동일한 문자열이 존재하는지 탐색하는 알고리즘을 구현해야한다. 

 

구현

실패 과정) 문제를 해결하기 위해 가장 먼저 생각해 본 방법은, 문자열 집합을 이루는 \(N\) 개의 문자열을 길이 별로 1차적으로 분류하는 방법이었다. 시퀀스 컨테이너와 연관 컨테이너를 복합적으로 사용하여 이를 구현하고자 했다. 연관 컨테이너 중의 하나인 STL의 std::map 클래스를 활용하여 Key로 문자열의 길이를, Key에 해당하는 map 요소로는 std::string 클래스를 요소로 가지는 std::vector 클래스를 사용하는 방법이다. 따라서 처음에 주어지는 \(N\) 개의 문자열을 각각 입력받을 때, 문자열의 길이를 확인하고 같은 길이를 가지는 문자열들끼리 하나의 std::vector<std::string> 형식의 동적 배열에 저장하는 방법을 시도해보았다.

 

// 의사 코드
using namespace std;

while (N--)
{
	string str;
	cin >> str;

	if (Map.at(str의 길이) NOT exists?)
	{
		vector<string> temp;
		Map.emplace(str의 길이, temp);
	}
	
	Map.at(str의 길이).push_back(str);
}

 

위와 같은 알고리즘으로 코드를 짜고 의기양양해서 문제가 풀리겠거니~ 하고 실행해봤지만 테스트 케이스의 3 %도 실행하지 못한 채 시간 초과 판정을 받아버렸다. '시간 초과가 대체 왜 날까?' 하고 곰곰이 생각해보다가 한 가지 사실을 깨달았다. 극단적으로 생각해보았을 때, \(N\) 개의 문자열과 \(M\) 개의 문자열의 모두 동일한 길이를 가지면 위 알고리즘은 아무런 실행 속도 향상을 꾀할 수 없는 바보 알고리즘이 되어버린다는 것이었다.

 

실패 요인 분석) 즉, 문자열의 길이만으로 1차적인 필터링을 수행하는 것은 전혀 적합하지가 않다는 것이다. 이 문제점은 그림으로 살펴보면 더 이해가 잘 된다.

 

그림을 못그려서 죄송

 

결국 위와 같이 너무 다양한 문자열이 같은 key로 매핑이 될 수 있다는 것이다. 여기서 위와 같이 생각하면서,

 

나는 지금 주어진 문자열들을 어떠한 자연수의 집합으로 대응시키는
매핑(즉 '사상' 또는 '함수')을 만드는 중이었던 거네?
그러면 문자열을 지금보다 더 다양하게 퍼트려져서 매핑되도록 할 수는 없을까?
아니면... 문자열마다 어떠한 고유한 식별 값(ID)을 가지게 할 수는 없을까?

 

 

 

라는 생각을 해보게 되었다(나는 수학 전공자니까...). 문자열마다 고유한 식별값을 가질 수 있으면, 이론상 단 한 번만의 연산으로 문자열의 비교가 가능해지는 것이다. 이렇게 생각을 곰곰이 하던 중, 문제의 힌트를 좀 살펴보고자 스크롤을 아래로 내려서 '알고리즘 분류' 부분을 살펴봤는데 눈에 바로 들어온 단어가 있었다...

 

---

 

해싱(hashing)이란 주어지는 임의의 길이의 데이터를 어떠한 고정된 길이의 값으로 변환하는 알고리즘을 말한다. 즉, 임의의 길이의 데이터에 대하여 고정된 길이의 값으로 대응하는 함수(해시 함수)를 만드는 알고리즘이다. 이렇게 이론적으로 말하면 어렵지만 이 문제에 적용하면, 문자열을 자연수로 대응시키는 것 역시 해시 알고리즘이라고 볼 수 있는 것이다. 위에서 내가 했던 작업은 일종의, 해싱 알고리즘을 만들고 있는 것이었고, 문제점은 내가 만든 해시 함수가 쓰레기좋은 해시 함수가 아니라는 것이었다. 그래서 너무 많은 수의 문자열이 같은 해시 코드를 가지게 되는 것(과도한 해시 충돌)이 문제였다.

 

알고리즘 개선) 문자열에 대한 간단한 해시 알고리즘을 찾아본 결과, 다항 롤링 해시(polynomial rolling hash)라는 비교적 내가 이해하기 쉽고 구현이 간단한 알고리즘을 찾았다.

위와 같이 문자열(문자의 배열) 내에서 인덱스 별로 각 문자를 나타내는 값(예를 들면, 단순히 char 형의 값으로 나타내는 값이거나 아니면 a = 1, b = 2 등으로 대응시킨 값, 두 가지 모두 해봤는데 똑같이 잘 실행된다)과 인덱스 별 \(a\)의 거듭제곱과 곱한 값을 전부 더해 \(H\)를 구한 뒤, 적당히 큰 소수 \(n\)으로 나누고 난 나머지 값을 해시 코드로 사용하는 방법이다. 여기서 사용하는 \(a\)의 값과, \(n\)의 값을 잘 정하면 해시 충돌의 가능성이 낮아져 적절한 성능의 해시 함수가 될 수 있다고 한다. 일반적으로는 \(a\)의 값으로는 가능한 문자의 경우의 수보다 큰 소수 중에서 가장 작은 값(또는 그 수의 역수), \(n\)의 값으로는 그냥 적당히 큰 소수를 사용하는 것 같다. 그래서 나는 \(n\)의 값을 4,565,710,823로 정해서 썼다(아무 의미 없는 그냥 큰 소수임).

* 롤링 해시를 사용하는 알고리즘을 라빈-카프(Rabin-Karp) 알고리즘이라고 부르는 것 같다.

 

위에서 알아본 polynomial rolling hash 방법으로 해시 함수를 변경하여 다시 코딩하여 문제를 제출한 결과 다행히 성공적으로 문제를 해결할 수 있었다. 단, 문제를 해결할 때 위와 같은 해시 함수를 사용하더라도 주어지는 문자열마다 반드시 서로 다른 자연수 값으로 매핑이 된다고는 장담할 수는 없었다. 길이가 500인 영소문자로만 구성되는 문자열의 가능한 경우의 수만 따져봐도 \(26^{500}\) 이라는 천문학적인 수가 나오는데 이론상(위의 알고리즘 기준) 0부터 \(n-1\) 까지의 해시 코드로만 매핑될 수 있기 때문이다. 그래서 기존의 map 구조를 똑같이 사용하되, key를 문자열의 길이가 아닌 문자열의 해시 코드가 되도록 수정하여 사용하였다.

 

아니 근데 이미 문제를 풀고 나서 보니까 그냥 STL 안에 해시 맵이랑 해시 멀티맵이 이미 구현되어 있다 ㅡㅡ 당연히 내가 만든 코드보다 당연히 합리적이고 효율적인 코드로 이루어져있을테니 저걸 활용하면 아마 실행 속도가 더 빠를 것 같다. 공부 겸 직접 해시 알고리즘을 적용해서 맵을 구현해본 것에 만족해야겠다...

 

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

#include <iostream>
#include <string>
#include <vector>
#include <map>

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

using namespace std;

// polynomial rolling hash
size_t HashFunction(string str)
{
	size_t hash = 0;
	size_t power = 1;
	for (char c : str)
	{
		hash += power * (c - 'a' + 1);
		power *= PRIME;
	}

	return hash % MODULO;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	map<size_t, vector<string>> HashTable;

	int N, M, Count = 0;
	cin >> N >> M;

	while (N--)
	{
		string str;
		cin >> str;

		vector<string> temp;
		size_t hash = HashFunction(str);
		HashTable.try_emplace(hash, temp);
		HashTable.at(hash).push_back(str);
	}

	while (M--)
	{
		string query;
		cin >> query;

		size_t hash = HashFunction(query);
		auto iter = HashTable.find(hash);
		if (iter != HashTable.end())
		{
			for (const string& str : (*iter).second)
			{
				if (query == str)
				{
					Count++;
					break;
				}
			}
		}
	}

	cout << Count << "\n";

	return 0;
}

 

실행 결과

* 아래의 두 개의 시간 초과는 문제 해결에 실패했을 때의 결과임.

 

---

 

해시 알고리즘을 처음 공부할 때에는 뭔가 굉장히 어렵다고 생각을 했는데 막상 이를 적용하는 문제를 직접 해결해보니 생각보다는 어렵지 않았던 것 같다. 물론 간단한 해시 알고리즘을 사용해서인데, 해시 충돌이 최대한 덜 일어나도록 해시 함수를 구현하는 것은 굉장히 어려운 일일 것이다. 그렇지만 간단한 해시 알고리즘을 사용했는데도 불구하고 실행 속도가 이렇게 향상되는 것을 보니 정말 신기했고, 해시 알고리즘이 얼마나 중요한 알고리즘인지를 알게 되었다.

 

그나저나 너무 글을 이상하게 써놔서 다른 사람이 내 생각을 이해할 수 있을지 모르겠다... 다른 사람이 이해하기 쉽게 설명하는 것도 연습이 필요한 것 같다.