BOJ 1544 사이클 단어

문제

1544번 사이클 단어

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 3685 2271 1888 64.547%

 

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

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

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

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

예제 입력 1 

5
picture
turepic
icturep
word
ordw

예제 출력 1 

2

예제 입력 2 

7
ast
ats
tas
tsa
sat
sta
ttt

예제 출력 2 

3

예제 입력 3 

5
aaaa
aaa
aa
aaaa
aaaaa

예제 출력 3 

4

코드

아 XX 미래를 위해 문제 풀고 있었는데 백준 섭종해버려서 미치겠다

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    char = [input().strip() for _ in range(n)]
    words = []

    for word in char:
        stack = list(word)
        is_same = False

        for _ in range(len(word)):
            rotated = ''.join(stack)
            last = stack.pop()
            stack.insert(0, last)
            
            if rotated in words:
                is_same = True
                break
        
        if not is_same:
            words.append(word)
    
    print(len(words))

 

해당 단어가 이미 등장한 단어가를 회전해서 만들 수 있는가?를 체크한다.

가능하다면 같은 단어이므로 버리고, 불가능하다면 새로운 단어이므로 저장한다.

 

words는 서로 다른 사이클 단어의 대표 집합이다.

이제 char에서 word를 하나씩 꺼내서 대표인지, 그리고 회전한 단어와 같은지 체크한다.

words = []

for word in char:

 

word의 단어를 하나씩 분리하여 stack에 저장한다.

stack = list(word)

그러면 다음과 같다.

"word" -> ['w', 'o', 'r', 'd']

 

이제 단어를 회전해야 하는데, len(word)만큼 돌아야 회전 경우 모두를 충족하게 된다.

회전은 stack의 마지막을 제거하여 맨 앞으로 삽입한다. (문제의 시계방향 충족)

last = stack.pop()
stack.insert(0, last)

 

예:

['w','o','r','d']
→ pop() → 'd'
→ insert(0,'d')
→ ['d','w','o','r']

 

그렇게 회전된 단어가 이미 저장된 단어와 같은지를 체크하고, 맞다면 종료한다.

if rotated in words:
	is_same = True
    break

 

word의 개수만큼 다 회전했는데도 못찾는 경우에는 새로운 단어이므로, 대표 단어 words 리스트에 추가한다.

if not is_same:
	words.append(word)

 

이를 결과로 print하면 서로 다른 사이클 단어 개수를 알 수 있다.

print(len(words))

 

 

예시

입력:

picture
turepic

 

1. picture:

words = [] 이고 비교대상이 없으므로 picture가 words 안에 들어가 대표 단어가 된다.

 

2. turepic

회전하면 다음과 같다.

turepic
cturepi
icturep
picture  ← 여기서 걸림

 

picture이라는 단어가 이미 있으므로 같은 단어임을 알 수 있으며, 따라서 추가하지 않는다.

 

정리

1. 단어 하나 선택
2. 가능한 모든 회전 생성
3. 기존 단어와 비교
4. 같으면 버림 / 다르면 추가

 

 

 

추가 코드

사실 '문자열 회전'이라고 하면 deque의 rotate 부터 생각이 난다.

따라서 deque로 풀어보았다.

from collections import deque
import sys
input = sys.stdin.readline

for __name__ == "__main__":
    n = int(input())
    words = []

    for _ in range(n):
        word = input().strip()
        q = deque(word)
        is_same = False

        for _ in range(len(word)):
            rotated = ''.join(q)

            if rotated in words:
                is_same = True
                break

            q.rotate(1)   # 오른쪽으로 한 칸 회전

        if not is_same:
            words.append(word)

    print(len(words))

 

그리고 사실 다른 분들 코드를 보고 배웠는데, 문자열 회전에서는 word + word 방식을 사용하는 방법도 있다.

어떤 단어를 두 번 붙이면 그 안에 모든 회전 형태가 들어있기 때문이다.

word + word = wordword

라는 형태에서는

word
ordw
rdwo
dwor

와 같은 형태가 전부 포함되어 있다.

 

따라서 아래와 같이 쉽고 빠르게 확인할 수 있다는 것이다. (황당~)

"turepic" in "picturepicture"

 

따라서 이렇게 쓸 수 있다.

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    words = []

    for _ in range(n):
        word = input().strip()
        is_same = False

        for saved in words:
            if len(word) == len(saved) and word in saved + saved:
                is_same = True
                break

        if not is_same:
            words.append(word)

    print(len(words))

 

아래 코드로 길이가 같고, word가 saved를 두 번 붙인 문자열 안에 있으면 word는 saved의 회전이다를 확인할 수 있다.

if len(word) == len(saved) and word in saved+saved: