[엘리스] 팰린드롬

팰린드롬 만들기

팰린드롬이란, 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 말한다. 예를 들어, “aba”, “abdba”, “abffba” 는 모두 팰린드롬이다.

 

임의의 문자열이 주어질 때, 몇 개의 문자를 적당히 삭제하면 이를 팰린드롬으로 만들 수 있다. 예를 들어, "abca"가 주어질 경우, 알파벳 'b’를 삭제하면 "aca"가 되므로, 팰린드롬으로 만들 수 있다.

 

임의의 문자를 제거함으로써 주어진 문자열을 팰린드롬으로 만들고 싶다고 할 때, 제거해야 하는 문자의 최소 개수를 출력하는 프로그램을 작성하세요.

입력

첫 번째 줄에 문자열이 주어진다. 문자열의 길이는 3000을 넘지 않는다.

출력

팰린드롬을 만들기 위해 제거해야 하는 문자의 개수의 최솟값을 출력한다.

입력 예시 1

abcfba 

출력 예시 1

1 

입력 예시 2

abcdefg

출력 예시 2

6

풀이

팰린드롬인지 확인하는 방법은 동적 계획법을 이용해 풀 수 있습니다. 그 이유는 abcfba에서 양쪽의 끝이 같은 경우, bcfb만 비교하면 되기 때문입니다. 하지만, 여기에서는 팰린드롬을 만들기위해서 몇개의 값을 제거해야하는 지 갯수를 계산해야 합니다. 진행되는 과정을 차례대로 보면 아래와 같습니다.

• data[start] == data[end]이면, T[start+1][end-1]와 같음
  • 예 : abcfba == bcfb
• data[start] != data[end]이면, T[start+1][end], T[start][end-1]의 최솟값에 1을 더하기
  • 예 : abcfb은 abcf와 bcfb중에서 최솟값에 1을 더하기
  • 이게 가능한 이유는 왼쪽의 값을 삭제하는 경우와 오른쪽의 값을 삭제하는 경우 두가지로 나뉘기 때문에

import sys

def palindrome(data) :
    '''
    문자열 data가 주어질 때, 이를 팰린드롬으로 만들기 위해 제거해야 하는 문자 개수의 최솟값을 반환하는 함수를 작성하세요.
    '''
    n = len(data)
    T = [[0 for i in range(n)] for j in range(n)]

    # 맨 마지막의 위치부터 시작 ba에서부터 진행해서 abcfba까지 진행 
    # ba -> fb -> fba -> cf -> cfb -> cfba -> bc -> bcf -> 
    # bcfb -> bcfba -> ab -> abc -> abcf -> abcfb -> abcfba
    for i in range(n-2,-1,-1) :
        for j in range(i+1,n) :
            if data[i] == data[j] :
                T[i][j] = T[i+1][j-1]
            else :
                T[i][j] = min(T[i+1][j], T[i][j-1]) + 1

            print(data[i], data[j], T)

    # 마지막의 T[0][n-1]에 있는 값을 출력하면 됨 
    return T[0][n-1]

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    s = input()

    print(palindrome(s))

if __name__ == "__main__":
    main()

이러한 팰린드롬을 좀 더 응용해서 팰린드롬을 만들 수 있는데, 예를 들어 abcfba이 들어오면 만들 수 있는 팰린드롬 중 하나인 abcba가 출력되는 형태이다.

• Link라는 테이블을 생성
  • 양 끝이 같은 경우 : 1을 삽입
  • abcfb은 abcf와 bcfb중에서 최솟값인 경우를 기록
    • 왼쪽을 늘리는게 최소인 경우 : 2을 삽입
    • 오른쪽을 줄이는게 최소인 경우 : 3을 삽입

import sys
sys.setrecursionlimit(10000)

def getActualPalindrome(data, s, e, Link) :
    print(s, e)
    if s > e :
        return ""
    if s == e :
        return data[s]
    else :
        if Link[s][e] == 1 :
            return data[s] + getActualPalindrome(data, s+1, e-1, Link) + data[s]
        elif Link[s][e] == 2 :
            return getActualPalindrome(data, s+1, e, Link)
        else :
            return getActualPalindrome(data, s, e-1, Link)

def getPalindrome(data) :
    '''
    문자열 data가 주어질 때, 이를 팰린드롬으로 만들기 위해 제거해야 하는 문자 개수의 최솟값을 반환하는 함수를 작성하세요.
    '''

    n = len(data)

    Table = [ [ 0 for i in range(n) ] for j in range(n) ]
    Link = [ [ 0 for i in range(n) ] for j in range(n) ]


    for i in range(n-1, -1, -1) :
        Table[i][i] = 0

        for j in range(i+1, n) :
            if data[i] == data[j] :
                Table[i][j] = Table[i+1][j-1]
                Link[i][j] = 1
            else :
                if Table[i+1][j] < Table[i][j-1] :
                    Link[i][j] = 2
                else :
                    Link[i][j] = 3

                Table[i][j] = min(Table[i+1][j], Table[i][j-1]) + 1
    return getActualPalindrome(data, 0, n-1, Link)

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    s = input()

    print(getPalindrome(s))

if __name__ == "__main__":
    main()

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn