[Silver IV] 사이클 단어 - 1544 (구현)

[Silver IV] 사이클 단어 - 1544

문제 링크

성능 요약

메모리: 32424 KB, 시간: 96 ms

분류

브루트포스 알고리즘(bruteforcing), 자료 구조(data_structures), 해시를 사용한 집합과 맵(hash_set), 구현(implementation), 문자열(string)

문제 설명

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

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

입력

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

출력

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

from collections import deque
n = int(input())
array = []
a = deque()
for i in range(n):
    s = deque(input())
    a.append(s)
    
while a:
    cnt = 0
    tmp = a.popleft()
    for i in range(len(tmp)):
        tmp.append(tmp.popleft())
        if tmp in array:
            cnt += 1
    if cnt == 0:
        array.append(tmp)
print(len(array))

1.입력받은 문자열 길이만큼 원형으로 나올 수 있는 문자열을 deque을 이용하여 다 꺼내보며 중복된 게 있는지 확인한다.

2.중복된 게 존재하지 않을 때만 값을 리스트에 담아주고, 리스트의 길이를 구하면 해결.