[백준 10942] 팰린드롬? (python)

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

10942번: 팰린드롬?

팰린드롬? 문제

주어진 수열에서 수열의 S번째부터 E번째까지 숫자들이 팰린드롬을 이루고 있는지 체크하는 문제

다이나믹 프로그래밍을 이용하여 해결할 수 있었다.

📌 문제 접근 포인트

1. 팰린드롬의 조건에 대해서 생각해보자. 팰린드롬의 경우 맨 앞에서부터 읽은 것이 뒤에서부터 읽은 것과 같은 경우이다.
2. 팰린드롬을 어떻게 구할지 생각해보자. 만약 단순하게 for문과 슬라이싱을 통해 모든 리스트를 탐색한다면 시간이 굉장히 많이 소요되기 때문에 요구사항의 조건 시간안에 들어올 수 없다.
3. 그렇다면 팰린드롬을 다른방식으로 구해줄 방법을 생각해보자.
팰린드롬의 성질애 대해서 생각해보면, 맨 앞의 문자(start)와 맨 뒤의 문자(end)가 다를 경우 팰린드롬이 될 수 없고, 만약 같다면 맨 앞에서 두 번째 문자(start+1)부터 맨 뒤에서 두 번째 문자(end-1)까지가 팰린드로린 경우 해당 문자열이 팰린드롬 임을 알 수 있다.
예를 들어 입력 예제에 있는 [1 2 1 3 1 2 1]에 대해서 생각해보자
→ 1글자로 된 숫자들은 팰린드롬이다. (1)
→ 2글자로 된 숫자들의 경우 맨 앞과 맨 뒤의 숫자가 같은지 체크해주면 된다. (2)
→ 3글자로 된 숫자들의 경우 맨 앞과 맨 뒤의 숫자가 같은지 여부를 먼저 체크해주고, 나머지 가운데가 팰린드롬인지 체크하면 된다. 이때, 가운데 들어가는 숫자가 팰린드롬인지 체크는 (1)에서 확인했으니, (1)번을 사용해서 체크해주면 된다. (3)
→ 4글자로 된 숫자들의 경우 맨 앞과 맨 뒤의 숫자가 같은지 여부를 먼저 체크해주고, 나머지 가운데가 팰린드롬인지 체크하면 되는데, 이때, 가운데에 들어가는 숫자가 팰린드롬인지 체크는 (2)에서 확인했으니, (2)번을 사용해서 체크해주면 된다.(4)
→ 5글자로 된 숫자들의 경우 맨 앞과 맨 뒤의 숫자가 같은지 여부를 먼저 체크해주고, 나머지 가운데가 팰린드롬인지 체크하면 되는데, 이때, 가운데에 들어가는 숫자가 팰린드롬인지 체크는 (3)에서 확인했으니, (3)번을 사용해서 체크해주면 된다.(5)
이렇게 가운데 배열을 이전에서 가져오는 방식으로 다이나믹 프로그래밍을 구성할 수 있는 것을 알 수 있다.
4. 위 아이디어를 이용해서 조건을 나누어주고, 다이나믹 프로그래밍을 구성해주면 해결 할 수 있다.

반응형

⚙️ 내가 푼 정답 코드

import sys
N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
check = [[0]*N for _ in range(N)]

for i in range(N):
    for start in range(N-i):
        end = start + i # 회문 확인할 끝지점과 시작지점 설정
        if start == end : # 단어가 1글자면
            check[start][end] = 1 # 회문이니 체크
        elif num[start] == num[end] : # 첫문자랑 끝문자랑 같으면
            if start + 1 == end: # 단어가 2글자면
                check[start][end] = 1 #회문이니 체크
            elif check[start+1][end-1] == 1: # 만약 가운데 애들이 회문이면
                check[start][end] = 1 # 얘는 결국 회문이니 체크
for _ in range(M):
    S, E = map(int, sys.stdin.readline().split())
    print(check[S-1][E-1])