[백준/파이썬] 10942: 팰린드롬?

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

10942번: 팰린드롬?

문제 요약 : N개의 자연수를 가지고 M가지 질문을 한다. 시작점과 끝점이 주어졌을 때 N이 그 지점 사이에서 팰린드롬을 만족하면 1을 출력, 아니면 0을 출력한다.

 

예제 입력1

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

예제 출력1

1
0
1
1

 

약 1년전에 풀었던 문제인데도, 꽤 애를 먹었다.

요며칠 문자열 문자만 풀어서 그냥 아무생각없이 list reversed를 썼다가 시간초과가 떴다.

dp문제임을 힌트로 얻고 풀었던 문제..!🤨

 

 

📌 풀이 1)

나는 재귀를 사용하여서 풀었다.

먼저 dp를 만들어주고, visit 확인을 위해 -1을 넣어주었다.

만일 펠린드롬 함수를 넣었는데, -1이 아니라면 이미 계산한 적이 있는 값이기 때문에 그 값을 그대로 돌려준다.

아닐경우,

1. 시작점과 끝점이 같을 경우 = 무조건 펠린드롬, 1을 return한다.
2. 시작점과 끝이 같을 경우
   1. 시작 +1이 끝과 같을 경우 = 무조건 펠린드롬, 1을 return한다.
   2. 같지 않을 경우, 중간 값이 펠린드롬인지 확인하기 위하여 start+1, end-1한 값을 다시 펠린드롬 함수에 넣는다.

시작점과 끝이 같지 않을 경우 = 무조건 펠린드롬 아님

 

# 펠린드롬?
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

N = int(input())
hong = list(map(int,input().split(' ')))
dp = list([-2]*N for _ in range(N))

def palindrome(start,end):
    if dp[start][end] != -2 :
        return(dp[start][end])
    
    if start == end :
        return 1
    
    if hong[start] == hong[end] :
        if start + 1 == end :
            return 1
        else :
            dp[start][end] = palindrome(start+1,end-1)
            return(dp[start][end])
    else :
        return 0

                
for _ in range(int(input())):
    start,end = map(int,input().split(' '))
    print(palindrome(start-1,end-1))

그런데 예전에 푼 코드가 시간이 훨씬 짧길래 ,, 그 코드도 뜯어봤다

 

📌 풀이 2 )

dp를 전부 돌리고, 값을 출력하는 형식으로 진행하였다.

주어지는 S와 E의 지점은 주어진 문자열의 길이만큼 가능하다.

 

len은 문자열의 길이이다.

start는 그 문자열의 시작지점이다. len개 만큼 문자열이 주어지기 때문에, n개 전부 돌 필요없이 n-len만큼만 돌면된다.

end는 start에 len을 더한 값이다.

 

1. 시작과 끝이 같으면 펠린드롬이다.
2. 시작점의 숫자와 끝점의 숫자가 같으면,
   1. 시작점 +1 과 끝점이 같으면 펠린드롬이다.
   2. 중간값이 1이면 펠린드롬이다. -> 이게 가능한 이유는 len길이가 짧은 지점부터 서서히 채워졌기 때문이다.

처음에 len이 0일경우, dp[0][0], dp[1][1], ... ,dp[n][n]이 1로 채워진다.

len이 1일경우, dp[0][1], dp[1][2], ... ,dp[n-1][n]은 두 지점의 값이 같으면 1로 채워진다.

len이 2일경우, 예를들어 dp[0][2]일경우, dp[1][1]이 펠린드롬이면 채워진다. 마찬가지로 dp[n-2][n]까지 진행한다.

len이 3일경우, dp[0][3]은 dp[1][2]가 펠린드롬이면 펠린드롬이 된다.

 

이런식으로, 2-2는 언제나 확인할 수 있다. 굳이 재귀를 사용하지 않아도됨!

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]


for len in range(n):
    for start in range(n - len):
        end = start + len
        
        if start == end:
            dp[start][end] = 1
        elif numbers[start] == numbers[end]:
            if start + 1 == end: 
            	dp[start][end] = 1
            elif dp[start+1][end-1] == 1: 
            	dp[start][end] = 1
            

for _ in range(int(input())):
    s, e = map(int, input().split())
    print(dp[s-1][e-1])