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

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

10942번: 팰린드롬?

Problem

• 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
• 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.
• 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.
• 자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.
• 둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
• 셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
• 넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

SOL

 

팰린드롬이란걸 처음에는 몰라서, 찾아봐야했던 문제였다.

 

Panlindrom

문자열을 뒤집어도, 똑같은 글자를 팰린드롬이라고 한다. 예를들어, 요기요, 기러기, 숫자로 한다면 121,131,1234321 이 있다.

 

팰린드롬을 확인하는 가장 간단한 방법은, 반복문을 이용해서, 앞의 시작글자와 뒤의 시작글자가 같은지 확인하는 방법이 있고, 문자열을 뒤집어서 원래 문자열이랑 같은지 보는 방법, 동적프로그래밍을 이용하는 방법이 있다.

 

반복문을 이용한 팰린드롬

while 문을 용해서, S~E 까지 팰린드롬이 맞는지 하나하나 검사하는 완전탐색 방법을 이용한거다.

start는 하나씩 늘어가고 , end 지점은 하나씩 줄어들면서 앞,뒤가 팰린드롬을 이루는지 검사한다.

arr="abba"

def is_palindrome(s,e):
    while s<e:
        if arr[s] != arr[e]:
            return 0
        s+=1
        e-=1
    return 1

print(is_palindrome(0,3))

문자열 뒤집어서 팰린드롬인지 검사하기

이 방법은 사람에게 좀 더 직관적인 방법이다. 하지만, 컴퓨터한테는 그닥 효율적이지 못한 방법이다.

문자열을 뒤집는 과정에서 반복문을 1개를 더 쓰고, 문자열에 +연산을 하는건 매우 무거운 연산이므로 (문자열을 붙이려면, list처럼 O(1)이 아니다) 효율적이지 못한 방법이다.

def is_palindrome_reverse():
    str_reverse=""
    for s in arr:
        str_reverse=s+str_reverse
    for i in range(len(arr)):
        if arr[i] !=str_reverse[i]:
            return False
    return True

print(is_palindrome_reverse())

동적 프로그래밍을 이용한 팰린드롬

 

팰린드롬인지, 아닌지 검사할 때, 우리는 모든 경우를 봐줄 필요가 없다. 양끝이 똑같은지 검사하고, 양끝을 제외한 안의 부분수열이 팰린드롬을 인지/아닌지만 알면 된다.

예를들어, arr=1234321 이라고 하자

1234321

빨간색부분을 비교해준다음, 파란색 부분수열이 팰린드롬인지 확인하면, 우리는 빨간색만 비교하면 된다!

1234321

하지만, 이게 팰린드롬을 이루는지, 안이루는지 모르기 때문에, 우리는 파란색 부분 수열의 부분수열을 또 탐색해준다.

이런식으로, 재귀적으로 구현한다음, 메모이제이션 방법을 이용하면 우리는 s,e 지점만 정하면 s부터 e가지 팰린드롬을 이루는지 안이루는지 빠르게 탐색할 수 있게 된다.

 

Bottom Up 방식으로 구현하기

 

정의 : DP[s][e] = S부터 E까지 팰린드롬인지/아닌지 저장하는 배열 점화식 : if) arr[s]==arr[e] and DP[s+1][E-1] : DP[s][e] = True

 

반복문의 반복순서를 주의해서 봐야한다. 반복문이 삼각형 모양으로 upper diagnal 방식?으로 돌게된다.그림으로 생각하면, 2차원 배열에서 아래의 번호와 같은 순서로 반복을 돌게된다.

def chk_Palindrome():
    for idx in range(N):
        for start in range(N):
            #upper dignal 방식
            end=start+idx
            if end>=N:
                break
            if idx==0:
                DP[start][end]=True
                continue
            if idx==1:
                if arr[start]==arr[end]:
                    DP[start][end] = True
                    continue
            if arr[start]==arr[end] and DP[start+1][end-1]:
                DP[start][end] =  True

 

전체코드

#Is Palindrome?
# 거꾸로 해도 똑같은 글자 
# 예를들어, 1234123,121,131... 등등
import sys
input= sys.stdin.readline

N=int(input().rstrip())
arr=list(map(int,input().split()))
M=int(input().rstrip())

DP=[[False for _ in range(N)] for _ in range(N)]

def chk_Palindrome():
    for idx in range(N):
        for start in range(N):
            #upper dignal 방식
            end=start+idx
            if end>=N:
                break
            if idx==0:
                DP[start][end]=True
                continue
            if idx==1:
                if arr[start]==arr[end]:
                    DP[start][end] = True
                    continue
            if arr[start]==arr[end] and DP[start+1][end-1]:
                DP[start][end] =  True

def Is_Palindrome(a,b):
    if DP[a-1][b-1]:
        return True
    else:
        return False

chk_Palindrome()
for i in range(M):
    a,b=map(int,input().split())
    if Is_Palindrome(a,b):
        print(1)
    else:
        print(0)