[백준/CPP] 사이클 단어 - 1544번

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

1544번: 사이클 단어

어떻게 풀어야 할지 감이 안 잡혀서 문제 태그를 보았다.

해시 테이블을 사용하는 것을 알고 감을 잡을 수 있었다.

 

- 풀이- 

1. 입력 받은 단어를 해시 테이블에서 검색한다. (set 사용)

2. 검색한 단어가 존재하지 않는다면 해당 문자열을 원형 큐처럼 돌리며 모든 경우를 해시 테이블에 넣어놓는다.

2-1. 정답 카운트를 1 늘린다.

 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

void swapStr(string& str) {
	// 맨 앞 문자열을 저장하고
	char tmp = str[0];
    // 맨 앞 문자열을 삭제한다.
	str.erase(0, 1);
    // 맨 뒤에 추가해주면 원형 큐처럼 동작함
	str += tmp;
}

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

	int n; cin >> n;

	set <string> st;
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		string s; cin >> s;

		// 해시 테이블에 현재 값이 없다면 원형 큐처럼 돌며 모든 문자열을 넣을 것임
		if (st.find(s) == st.end()) {
			st.insert(s);
            // 첫 문자열은 넣어주었기 때문에 k는 1부터 시작하였음!
			for (int k = 1; k < s.length(); k++) {
				swapStr(s);
				st.insert(s);
			}
			cnt++;
		}
	}

	cout << cnt;

}

 

 

문제 태그를 안 보고 풀 수 있는 날이 왔으면 좋겠다.