BOJ 5555 - 반지

문제

BOJ 5555 - 반지

패턴 문자열과 N개의 링 문자열이 주어진다. 각 링은 원형으로 연결된 문자열이다. 링을 어느 위치에서 시작해서 읽어도 패턴이 포함되면 카운트한다. 패턴을 포함하는 링의 수를 출력한다.

입력

• 첫 줄: 패턴 문자열
• 다음 줄: 링의 수 N (1 ≤ N ≤ 100)
• 다음 N줄: 각 링 문자열

출력

패턴을 포함하는 링의 수를 출력한다.

예제

풀이

원형 문자열의 특성을 이용해, 링 문자열을 두 번 이어 붙이면 모든 회전 상태를 포함한 문자열이 된다. 이 문자열에서 패턴의 존재 여부를 검사한다.

1. 패턴 문자열을 입력받는다.
2. 각 링 문자열을 자기 자신과 이어 붙여(ring + ring) 이중 문자열을 생성한다.
3. 이중 문자열에 패턴이 포함되어 있으면 카운트를 증가시킨다.
4. 최종 카운트를 출력한다.

핵심 아이디어: 원형 문자열 회전 탐색의 고전적 트릭인 '문자열 두 번 이어 붙이기'를 사용한다. 길이 L인 링을 두 번 이어 붙이면 L개의 모든 회전을 포함하므로, 단순 in 연산자로 O(N) 탐색이 가능해진다.

코드

import sys
 
input = sys.stdin.readline
 
pattern = input().strip()
N = int(input())
count = 0
 
for _ in range(N):
    ring = input().strip()
    doubled = ring + ring
    if pattern in doubled:
        count += 1
 
print(count)

복잡도

• 시간: O(N²)
• 공간: O(N)