[백준][파이썬][팰린드롬][LCS] 5502번: 팰린드롬

관련 문제들

 

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

 

 

문제

팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 되게 되는 문자의 개수를 구하는 프로그램을 작성하여라.

예제에서는, 2개의 문자를 삽입하여 팰린드롬이 된다. "Ab3bd"는 "dAb3bAd" 혹은 "Adb3bdA" 로 바뀔 수 있다. 하지만, 2개 미만의 문자를 삽입해서는 팰린드롬이 될 수 없다.

입력

첫 번째 줄에는 문자열의 길이 N (3 ≤ N ≤ 5000)이 주어진다. 두 번째 줄에는 길이가 N인 문자열이 주어진다. 문자열은 대문자 'A'-'Z'와 소문자 'a'-'z', 숫자 '0'-'9'로 이루어진다. 대문자와 소문자는 구분되어야 한다.

출력

첫 번째 줄에 삽입해야할 최소 개수를 출력한다.

예제 입력 1 복사

5
Ab3bd

예제 출력 1 복사

2

 

---

 

 

• LCS(최장 공통 부분 수열): 주어진 문자열과 그 역순 문자열 간의 LCS를 구하면, 팰린드롬에서 변하지 않는 부분의 길이를 알 수 있습니다.
• 삽입해야 할 문자 수 계산: 전체 문자열의 길이에서 LCS 길이를 뺀 값이 최소 삽입해야 할 문자의 개수가 됩니다.

 

1. 입력 받는 단어를 거꾸로 해서 2개의 단어를 준비한다.

2. 두 단어에서 순서를 유지하며 공통된 단어의 수를 구한다 : LCS라고 두 개의 문자열에서 순서를 유지하며 공통된 부분 수열 중 가장 긴 값을 구하는 알고리즘이 있다. 

3. 두 단어에서 공통된 가장 긴 문자열의 길이를 찾았다. 그럼 단어길이에서 공통된 부분 수열의 길이를 빼주면  "삽입해야할 최소 개수"를 구할 수 있다.

 

예를 들어 " Ab3bd"에 순서를 뒤집으면 "db3bA"이고 여기에 LCS는 {b, 3,b}이다.

5 - 3 = 2이다.  

 

import sys 

# 입력받은 단어를 거꾸로 해서 순서가 유지된 가장 긴 공통 부분 수열을 구하고
# 처음에 입력받은 단어길이에서 빼준다. 그럼 "삽입해야할 최소 개수"를 구할 수 있다.
def solution(word):
    N = len(word)
    
    # 주어진 문자열의 역순
    rev_s = word[::-1]
    
    # DP 테이블 생성 (LCS를 계산하기 위한 DP 테이블)
    # 단어의 글자수 + 1 길이만큼 리스트 
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    
    # LCS 계산
    # word와 rev_s의 문자를 비교하기 위해 이중 for문 
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            # word의 i번째와 rev_s의 j번째 글자 확인 
            if word[i - 1] == rev_s[j - 1]:
                # 이전까지의 LCS 길이 + 1 
                dp[i][j] = dp[i - 1][j - 1] + 1 # 즉, 현재 위치(i, j)에서 비교한 문자 이전까지의 최대 공통 부분 수열의 길이입니다.
            # 만약 두 문자가 다르다면
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # 최소 삽입 횟수는 전체 문자열 길이에서 LCS 길이를 뺀 값
    lcs_length = dp[N][N]
    
    # 아하! 두 개의 문자열에서 순서를 유지하며 공통된 부분 수열 중 가장 긴 값(LCS)을 찾고 
    # 전체 길이에서 가장 긴 공통 부분 수열 값을 빼주면 "삽입해야할 최소 개수"를 구할 수 있겠구나 
    return N - lcs_length

if __name__=="__main__":
    N = int(input())
    word = input()
    
    print(solution(word))

 

 

이렇게도 나타낼 수 있다. 

 

import sys 
sys.stdin=open('input.txt', 'r')


def solution(N, word):
    word2 = word[::-1]
    
    dp = [[""]*(N+1) for _ in range(N+1)]
    
    for i in range(1,N+1):
        for j in range(1,N+1):
            if word[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1] + word[i-1]
            else:
                if len(dp[i-1][j]) > len(dp[i][j-1]):
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    
    print(dp[N][N])
    print(N - len(dp[N][N]))


if __name__ == "__main__":
    N = int(input())
    word = input()
    
    solution(N, word)