알고스팟: Jaeha’s Safe (ID: JAEHASAFE)

[문제 링크]

algospot.com :: JAEHASAFE

---

KMP 알고리즘이 활용되는 문제가 정말 많은거 같다.

 

금고를 반시계방향으로 돌려서 맞추는 횟수는 shifts(a, b) 함수의 반환값을 통해 알 수 있다.

 

돌리기 전 문자열을 a, 반시계 방향으로 돌리고 난 후 문자열을 b라고 했을 때 shifts(a, b) 를 수행하면 a문자열과 같은 문자열을 뒤에 붙인 문자열이 만들어지는데 이 문자열에서 b의 위치를 KMP 알고리즘을 통해 빠르게 구할 수 있다.

이 때 구한 b의 위치가 곧 돌린 횟수가 되므로 결과값에 누적시킨다.

 

문제를 해결하기 위해선 반시계방향, 시계방향으로 번갈아가며 돌려야 한다.

a문자열을 시계방향으로 돌려서 b문자열을 만드는데 돌리는 횟수와 b문자열을 반시계방향으로 돌려서 a문자열을 만드는 횟수가 같기 때문에 이를 이용하여 매개변수의 순서를 바꾼 shifts(b, a) 를 수행하면 동일한 결과를 얻을 수 있다.

---

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> getPartialMatch(const string& s)
{
	int len = s.size();
	vector<int> pi(len, 0);

	int begin = 1, matched = 0;
	while (begin + matched < len)
	{
		if (s[begin + matched] == s[matched])
		{
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}

int KMPsearch(const string& h, const string& s)
{
	int hLen = h.size(), sLen = s.size();
	int ret;
	vector<int> pi = getPartialMatch(s);

	int begin = 0, matched = 0;
	while (begin <= hLen - sLen)
	{
		if (matched < sLen && h[begin + matched] == s[matched])
		{
			matched++;

			if (matched == sLen)
			{
				ret = begin;
				break;
			}
		}
		else
		{
			if (matched == 0)
				begin++;
			else
			{
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return ret;
}

int shifts(const string& original, const string& target)
{
	return KMPsearch(original + original, target);
}

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int N;
		cin >> N;

		vector<string> s(N+1);
		for (int i = 0; i <= N; i++)
			cin >> s[i];

		int sum = 0;
		for (int i = 0; i < N; i++)
		{
			if (i % 2 != 0)
				sum += shifts(s[i], s[i + 1]);
			else
				sum += shifts(s[i + 1], s[i]);
		}

		cout << sum << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 138 day