문제링크: https://www.acmicpc.net/problem/1544

문제

사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다.

만약에 단어 A와 단어 B가 있을 때, 단어 B를 원형으로 써서, 단어 A와 같이 읽을 수 있으면, 두 단어는 같은 단어이다.

따라서, picture와 turepic은 같은 단어다.

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

입력

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 단어가 한 줄에 하나씩 주어진다. 단어는 영어 소문자로만 이루어져 있다. N은 50보다 작거나 같은 자연수이며, 단어의 길이는 최대 50이다.

출력

첫째 줄에 서로 다른 단어가 몇 개인지 출력한다.

풀이

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>

std::string makeString(std::queue<char>& q) {
	std::string str = "";
	for (int i = 0; i < q.size(); i++) {
		str += q.front();
		q.push(q.front());
		q.pop();
	}

	return str;
}

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

	int N; std::cin >> N;
	std::vector<std::string> v;

	for (int i = 0; i < N; i++) {
		std::string s; std::cin >> s;
		
		if (v.size() == 0) {
			v.push_back(s);
		}
		else {
			std::queue<char> q;

			for (int k = 0; k < s.size(); k++) {
				q.push(s[k]);
			}

			bool issame = false;

			for (int j = 0; j < v.size(); j++) {
				for (int k = 0; k < s.size(); k++) {
					std::string compstr = makeString(q);

					if (compstr == v[j]) {
						issame = true;
						break;
					}
					
					q.push(q.front());
					q.pop();
				}

				if (issame) {
					break;
				}
			}

			if (!issame) {
				v.push_back(s);
			}
		}
	}

	std::cout << v.size() << "\n";

	return 0;
}

Queue
FIFO의 특성을 가지는 자료구조.
주로 push와 pop을 사용해 문제를 해결한다.

빈 vector를 선언해두고 string을 queue에 넣고 돌리며 같은 문자열이 있으면
vector에 추가를 하지 않고, 같은 문자열이 없으면 vector에 문자열을 추가한다.
그렇게 최종적으로 vector에 들어가있는 문자열의 개수가 다른 문자열의 개수이다.

노트

사실 queue를 안 쓰고, string의 erase() 메서드를 사용 할 수도 있었으나,
사이클, 회문 등의 문제를 보면 자동적으로 queue가 떠올라 queue를 사용해 구현했다.
그래서인지 현재 푼 방법이 이 문제에서의 최선의 방법 같지는 않다.