백준 10266번: 시계 사진들 (Python)

접근

각도는 1부터 360,000까지의 값을 가진다. 각 시계에 해당하는 0의 요소를 360,000개 가진 리스트 두 개를 만들고, 각각의 시계 사진이 가지는 각도 값들에 해당하는 요소를 1로 바꾸어준다. 그리고 KMP 알고리즘을 이용하여 두 개의 리스트를 비교하면 된다.

주의할 점은 360,000 각도를 지나가서 일치할 수 있기 때문에 첫 번째 시계를 두번 반복해서 표시한다.

ex ) [0, 1, 2, 3, 4] [359998, 359999, 0, 1, 2] 왼쪽 두개의 시계 사진은 모두 바늘끼리 1 차이가 나는 5개의 바늘을 표시하고 있지만, 위의 주의점을 확인하지 않으면 KMP 알고리즘을 이용하여 일치하는지 확인할 수 없다.

2021.06.18 - [코딩/백준 (Python)] - 백준 1786번: 찾기 (Python)

백준 1786번: 찾기 (Python)

코드

import sys


def kmptable(a):
    m = len(a)
    table = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and a[i] != a[j]:
            j = table[j - 1]
        if a[i] == a[j]:
            j += 1
            table[i] = j
    return table


def kmp(s, p):
    table = kmptable(p)
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = table[j - 1]
        if s[i] == p[j]:
            if j == len(p) - 1:
                return True
            else:
                j += 1
    return False


n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

clock1 = [0] * 360000
clock2 = [0] * 360000

for i in a:
    clock1[i] = 1
for i in b:
    clock2[i] = 1

clock1 += clock1

if kmp(clock1, clock2):
    print("possible")
else:
    print("impossible")

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!