백준 1544: 사이클 단어

문제 요약

사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 단어 A와 단어 B가 있을 때, 단어 B를 원형으로 써서, 단어 A와 같이 읽을 수 있으면, 두 단어는 같은 단어이다. 따라서, picture와 turepic은 같은 단어다.

N개의 단어가 주어졌을 때, 서로 다른 단어가 총 몇 개인지 구하는 프로그램을 작성하시오.

문제 분류

• 구현
• 자료 구조
• 문자열
• 브루트포스 알고리즘
• 해시를 사용한 집합과 맵

문제 풀이

문자열을 그대로 사용하기는 어렵고, 해시함수를 이용해 문자열을 적당한 int로 바꿔주고 그 수를 이용하여 비교하면 좋을 것 같았다.

나는 해시함수를 직접 만들었는데, 입력이 "abc" 일 경우, (1*27^2 + 2*27 + 3 : a가 1, b가 2, c가 3, 자릿수마다 27에서 제곱)의 값에서 소수인 7919의 나머지를 취해주었다.

그리고 해시함수가 같은 경우도 포함하여 mutlimap의 자료구조를 이용하였다. key는 해시값으로, value는 문자열로 하여, key(해시값)이 같더라도 value(문자열)이 서로 같지 않으면 다른 문자열로 파악하였다.

또한 문자열의 순환에 대해서는 맨 앞의 문자를 맨뒤로 보내는 작업을 length()번 해줌으로써 해결했다.

pow()를 사용할 때에는 백준에서 cmath헤더를 포함해주어야 한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>

using namespace std;

int hashing(string in) {
	unsigned long long int hash = 0;
	for (int i = 0; i < in.length(); i++)
		hash += (in[i] - 96) * pow(27, (in.length() - i - 1));
	return hash % 7919;
}
int main()
{
	int n, cnt = 0;
	int hash;
	bool sol;
	string in, temp;
	multimap<int, string> v;
	cin >> n;
	while (n--) {
		sol = true;
		cin >> in;
		for (int i = 0; i < in.length(); i++) {
			hash = hashing(in);
			auto it = v.equal_range(hash);
			if (it.first != v.end()) {
				for (auto r = it.first; r != it.second; r++) {
					if (r->second == in) {
						sol = false;
						break;
					}
				}
			}
			temp = in[0];
			in.erase(0, 1);
			in += temp;
		}
		if (sol) {
			hash = hashing(in);
			v.insert({ hash, in });
		}
	}
	cout << v.size();

	return 0;
}