BOJ 2641 - 다각형그리기

문제

BOJ 2641 - 다각형그리기

방향 수열로 다각형을 그린다 (1=위, 2=오른쪽, 3=아래, 4=왼쪽). 기준 다각형과 같은 모양인 후보를 찾아라. 시작점과 방향이 달라도 같은 모양이면 일치한다.

입력

기준 수열의 길이 N, 기준 수열, 후보 수와 후보 수열들이 주어진다.

출력

일치하는 후보의 수와 해당 수열들을 출력한다.

예제

풀이

순환 문자열 매칭과 역순 매칭으로 같은 다각형인지 판별한다.

1. 기준 수열을 2번 반복하여 순환 매칭이 가능하도록 한다
2. 역방향 수열은 방향을 반대로 변환(1↔3, 2↔4)하고 순서를 뒤집어 만든다
3. 후보 수열이 정방향 또는 역방향 순환 문자열에 포함되면 같은 다각형이다

핵심 아이디어: 시작점이 달라도 순환 매칭으로 처리하고, 반시계 방향은 역순 + 방향 반전으로 변환하여 비교한다.

코드

import sys
 
input = sys.stdin.readline
 
n = int(input())
s1 = input().strip().replace(" ", "")
s1 *= 2
table = str.maketrans("1234", "3412")
s2 = s1[::-1].translate(table)
answer = []
for _ in range(int(input())):
    x = input().strip()
    y = x.strip().replace(" ", "")
    if y in s1 or y in s2:
        answer.append(x)
print(len(answer))
print(*answer, sep="\n")

복잡도

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