[BOJ_Python]1544. 사이클 단어

문제

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

 

 

사용 알고리즘

구현

 

풀이

고려사항

1. 글자사이클 진행 시 같은 단어가 존재하는지

2. 글자수가 동일한지

 

후기

1. 이 문제의 keypoint는 단어의 사이클을 처리하는 것이다.

기준이 되는 단어를 두번 붙여놓으면(ex. picture -> picturepicture)

비교할 단어가 어디서부터 싸이클을 돌던지 상관없이 기준단어와 동일 단어인지 포함관계로 확인할 수 있다.

2. 하지만 이 방식은 아래와 같은 예시에서 함정이 존재한다.

같은 단어의 연속의 경우 포함관계로만 확인이 어렵기 때문에 기준 단어와 비교 단어의 길이 비교 조건이 추가되어야 한다.

때문에 아래와 같이 조건을 설정하였다.

if len(word) * 2 != len(standard) or word not in standard:

3. q를 사용하여 확인 시 while이 아닌 for문을 사용하였다.

이는 기준단어와 비교단어가 다를 경우 다시 q에 넣어주고 진행을 하기 때문에

q가 비어있을 때까지가 아닌 한바퀴만 검사하면 되기 때문이다.

 

코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
words = deque([input().rstrip() for _ in range(N)])
cnt = 0
while words:
    standard = words.popleft()
    standard *= 2
    len_words = len(words)
    for i in range(len_words):
        word = words.popleft()
        if len(word) * 2 != len(standard) or word not in standard:
            words.append(word)
    cnt += 1
print(cnt)

 

결과