[BOJ] 1053 팰린드롬 공장

thoho·2023년 1월 7일

코딩 문제 풀이

목록 보기

4/13

문제 푸는 내내 "아니 팰린드롬을 어떻게 DP로 풀어! 팰린드롬을 DP로 풀 생각을 어떻게 해!"라고 부르짖었다. 문제 태그를 보고 문제를 골라서 망정이지, 아니었으면 풀 수 있었을까? 싶다. 결국 혼자 힘으로 못 풀고 구글링으로 힌트를 좀 얻어서 풀었다.

문제 요약

팰린드롬(palindrome) : 문자의 순서를 뒤집어 읽어도 원래 문자열과 같은 형태가 되는 문자열.

문자열이 주어지고, 이 문자열을 팰린드롬으로 만들기 위해 다음의 4가지 연산을 최소 몇 번 사용해야하는지 출력한다(문제 설명이 굉장히 애매하게 써있다)

문자열의 어떤 위치에 어떤 문자를 삽입한다. (ex. abbca → acbbca)
문자열의 어떤 위치에 어떤 문자를 삭제한다. (ex. abbca → abba)
문자열의 어떤 위치에 있는 문자를 다른 문자로 바꾼다. (ex. abcaa → aacaa)
문자열의 2개의 문자의 위치를 서로 교환한다. (ex. abcbca → abccba)

단, 4번 연산은 최대 한 번만 사용할 수 있다.

설명

앞서 말했듯 DP 문제이다. DP를 이용해 부분적으로 펠린드롬을 만들기 위한 최소 횟수를 계산하고, 점점 범위를 늘려 마지막에는 문자열 전체를 팰린드롬으로 만들기 위한 최소 횟수를 계산한다.

DP 배열의 설계

우선, Bottom-Up 방식으로 구현하였다. 작은 단위의 dp 배열의 값을 채워나가며 최종적으로 원하는 값을 얻는 방식.

입력받은 문자열의 길이를 N이라 하고, 0 <= i < N, 0 <= j < N, i <= j라 할 때dp[i][j]를 문자열의 i 인덱스부터 j 인덱스까지를 팰린드롬으로 만들기 위한 최소 횟수라고 하자.

사실 각 단계에서 실제 문자열이 어떤 모양으로 고쳐지는지는 관련이 없다. 오로지 연산횟수만 계산하면 되기 때문. 그렇기에 삽입과 삭제연산은 사실상 같다. 이미 팰린드롬인 문자열에서 문자의 갯수를 하나 더 늘리고 팰린드롬으로 만든다면, 문자 하나를 삭제하거나 새로운 문자를 삽입해야하는데, 둘 다 연산 횟수는 각각 1번이기 때문.

DP 문제가 늘상 그러하듯, DP를 위한 가장 기저를 초기화해주어야한다. 이 문제에서는 문자가 1, 2개인 경우를 초기화해야한다. 문자가 1개인 경우(즉 i==j인 경우) dp[i][j] = 0, 문자가 2개인 경우 str[i] == str[j]라면 0(이미 팰린드롬이기 때문에), 그렇지 않으면 문자를 삭제하거나 삽입해야하므로 1로 초기화한다.

사용 횟수에 제한이 있는 4번 연산을 먼저 수행해 복잡성 줄이기

4번 연산에는 사용 횟수 제한이 있다. dp에서 늘 그러하듯 매번 단계마다 1, 2, 3, 4 연산을 수행하는 격우를 각각 고려할수도 있지만, 4번의 경우 사용 횟수또한 관리해야하므로 문제가 조금 복잡해진다.
물론 dp 배열을 3차원 배열로 만들어서 4번을 이미 사용한 경우, 아닌 경우를 따로 관리하는 방법도 있으나... 구글링을 해보니, 많은 사람들이 dp 계산을 시작하기 전, 4번을 먼저 수행하는 방법을 선택하고 있었다.

즉, 4번 연산을 통해 새로운 문자열을 생성하고, 해당 문자열로 dp 연산을 각각 수행하는 것.
'abc'라는 문자열이 있다면 abc, bac, cba, acb에 대해 연산을 수행한다.

매 단계에서의 연산

친구들이랑 풀이를 공유하다가 알게된 사실인데... 조금의 사담.
나는 dp를 풀 때 0부터 N까지를 순회하며, 해당 단계가 영향을 미칠 수 있는 다음 단계의 값을 갱신한다. 보통 현재 단계가 영향을 받을 수 있는 이전 단계의 값을 불러와서 지금 단계의 값을 만드는 듯.
결국 무슨 차이냐면, 0부터 N까지 순회하며, i단계로 만들 수 있는 다음 단계의 값을 갱신하는지, 현재 i단계의 값을 갱신하는지의 차이인듯. 단순 방식의 차이고, 나는 전자가 익숙해서 해당 방법으로 주로 문제를 해결한다. 이번에도 해당 방법으로 코드를 구현했다.

i부터 j까지는 이미 팰린드롬이라고 가정한다. dp[i][j]에는 i부터 j까지를 팰린드롬으로 만드는 최소 횟수가 저장되어있다. dp[i][j]가 영향을 미칠 수 있는 다음 단계는 다음과 같다.

dp[i][j+1] : i-1에 문자 하나를 삽입하거나 j+1을 삭제.
dp[i-1][j] : j+1에 문자 하나를 삽입하거나 i-1을 삭제.
dp[i-1][j+1] : i-1과 j+1이 같으면 이미 팰린드롬이고, 만일 같지 않으면 i-1이나 j+1을 교체.

편의상 어느 좌표의 값을 바꾸어야하는지 적었지만, 실제 문자열이 어떻게 팰린드롬이 되는지는 전혀 중요하지 않으며, i부터 j까지를 몇 번의 연산을 통해 팰린드롬으로 만들 수 있는지만이 중요하다. 그렇기에 글자를 삽입하거나 삭제함으로써 index가 바뀌는건 전혀 신경쓸 필요가 없다.

위의 3가지 단계는 다음과 같이 쓸 수 있다.

dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
dp[i-1][j] = min(dp[i-1][j], dp[i][j] + 1)
if str[i-1] == str[j+1] :
	dp[i-1][j+1] = min(dp[i-1][j+1], dp[i][j])
else :
	dp[i-1][j+1] = min(dp[i-1][j+1], dp[i][j] + 1)

지금 다음 단계에 저장된 값과, 현재 단계에 1을 더한 값을 비교해 더 작은 값을 넣는다. 이 과정을 i는 N-1부터 0까지, j는 0부터 N까지 순회하며 반복한다(i <= j인 경우에만 수행)

최종적으로 dp[0][[N-1]에 저장된 값이 해당 문자열을 팰린드롬으로 만들기 위해 필요한 최소 연산 횟수이다.

구현

org = list(input().strip())
length = len(org)

# 4번 연산을 수행하지 않은 경우에 대해 dp 연산 수행
minValue = makePelindrome(org)

# 4번 연산을 모든 자리에 대해 수행한 결과물로 각각 dp 연산 수행 
for i in range(length) :
  for j in range(length) :
    if org[i] == org[j] :
      continue
    org[i], org[j] = org[j], org[i]
    minValue = min(minValue, makePelindrome(org) + 1)
    org[i], org[j] = org[j], org[i]

print(minValue)

4번 연산을 미리 수행하고, 해당 결과에 대해 makePelindrome 함수를 호출하여 dp 연산을 수행한다.

def makePelindrome(str) :
  dp = [[MAX_SIZE for i in range(0, length)] for j in range(0, length)]

  dp[0][0] = 0
  dp[length-1][length-1] = 0

  # initializing. In case of the number of element is 1 or 2
  for i in range(1, length-1) :
    dp[i][i] = 0
    
    if str[i] == str[i+1] :
      dp[i][i+1] = 0
    else :
      dp[i][i+1] = 1
    
    if str[i-1] == str[i] :
      dp[i-1][i] = 0
    else :
      dp[i-1][i] = 1
  
  for i in reversed(range(0, length)) : # length-1 ~ 0
    for j in range(0, length) :         # 0 ~ length-1
      if i > j :
        continue
      if i-1 >= 0 :
        dp[i-1][j] = min(dp[i-1][j], dp[i][j] + 1)
      if j+1 < length :
        dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
      if i-1 >= 0 and j+1 < length :
        if str[i-1] == str[j+1] :
          dp[i-1][j+1] = min(dp[i-1][j+1], dp[i][j]) 
        else :
          dp[i-1][j+1] = min(dp[i-1][j+1], dp[i][j] + 1)
  
  return dp[0][length-1]