[백준/Python] 10942번: 팰린드롬?

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

10942번: 팰린드롬?

---

---

문제 분석

팰린드롬(palindrome)이란?

팰린드롬[나무위키]

회문 - 위키백과, 우리 모두의 백과사전

 

문제는 N개의 자연수 중 S번째 수부터 E번째까지의 수가 팰린드롬인지 판단하는 문제이다.

질문의 개수가 백만 개이며 팰린드롬을 백만 번 판단하게 된다면 문제의 시간제한인 0.5초를 넘어 시간 초과가 나오게 된다.

 

따라서 팰린드롬을 판단하는 것을 N개의 자연수가 입력되었을 때 바로 모든 경우의 수를 판단하고

질문을 받았을 때 바로 출력할 수 있도록 해야 한다.

 

우선, 질문을 받았을 때 판단해야 되는 수의 개수가 홀수인지 짝수인지 판단이 필요하다.

만약 홀수라면 가운데 수를 기준으로 양쪽이 같아야 하고, 짝수라면 반을 나누어 양쪽을 비교해야 한다.

 

어떻게 하면 모든 경우의 수를 판단할 수 있을까?

 

기준점이 필요하다.

N개의 자연수를 모두 기준으로 생각하고 양쪽을 하나씩 추가하면서 날개를 펼치듯 수를 늘려가며 판단하면 모든 경우를 판단할 수 있다.

 

7개의 수가 주어졌다고 가정하면 1번부터 기준을 잡는다.

 

1. 판단해야 되는 수의 개수가 홀수일 때

1. 1. 첫 번째 수, 마지막 번째 수를 기준으로 했을 때

모든 경우 중 숫자를 하나만 갖는 경우는 모두 팰린드롬이다.

즉, s = 1, e = 1일 경우 팰린드롬이 된다.

 

이제 양쪽을 펼치며 판단을 해야 한다.

하지만 첫 번째 수보다 앞에 있는 수가 없기 때문에 판단이 불가능하다. (인덱스의 범위를 넘어간 경우)

이런 경우 바로 함수를 종료한다.

 

1. 2. 첫 번째 수가 기준이 아닐 경우

만약 세 번째 수가 기준이라고 했을 때

첫 번째 경우와 같이 한 개를 판단하는 경우는 팰린드롬이므로 생략하고

양 쪽에 수를 하나씩 늘려 추가한다.

즉, s = 2, e = 4가 된다. 이 경우 팰린드롬이 아닌 경우라고 저장하면 된다.

 

이렇게 양쪽으로 수를 하나씩 늘려가며 판단해 s, e를 인덱스로 갖는 이차원 리스트에 팰린드롬 여부를 저장한다.

 

 

2. 판단해야 되는 수의 개수가 짝수일 때

2. 1. 첫 번째 수, 마지막 번째 수를 기준으로 했을 때

만약 판단해야 되는 수의 개수가 짝수라면 기준에서 바로 다음의 수를 같이 기준으로 정해 같은 방식으로 진행한다.

즉, 기준이 첫 번째 수와 두 번째 수가 되는 것이다.

 

2. 2. 첫 번째 수가 기준이 아닐 경우

위와 같이 세 번째 수가 기준이라면 세 번째, 네 번째 수가 기준이 되고

s = 2, e = 5 ... 와 같이 수를 판단할 수 있다.

 

위의 방식을 진행하면 모든 경우의 팰린드롬 여부를 확인할 수 있다.

팰린드롬 여부는 dp[s - 1][e - 1]로 이차원 배열에 저장하면 된다. (인덱스는 0부터이므로 1씩 빼주어야 함)

 

def pelCheck(start, end):
    while start > -1 and end < n:
        if arr[start] == arr[end]:
            pel[start][end] = 1
        else:
            break

        start -= 1
        end += 1

...

for i in range(n):
    # 판단 수가 홀수 개일 때
    pelCheck(i, i)
    # 판단 수가 짝수 개일 때
    pelCheck(i, i + 1)
    
...

---

코드

import sys

input = sys.stdin.readline


def pelCheck(start, end):
    while start > -1 and end < n:
        if arr[start] == arr[end]:
            pel[start][end] = 1
        else:
            break

        start -= 1
        end += 1


n = int(input())

arr = list(map(int, input().split()))

pel = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    pelCheck(i, i)
    pelCheck(i, i + 1)

m = int(input())

for _ in range(m):
    s, e = map(int, input().split())

    print(pel[s - 1][e - 1])