BOJ: 1053

Posted on In

문제

팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다.
모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다.

  1. 문자열의 어떤 위치에 어떤 문자를 삽입 (시작과 끝도 가능)
  2. 어떤 위치에 있는 문자를 삭제
  3. 어떤 위치에 있는 문자를 교환
  4. 서로 다른 문자를 교환

1, 2, 3번 연산은 마음껏 사용할 수 있지만, 마지막 연산은 많아야 한 번 사용할 수 있다.
문자열이 주어졌을 때, 팰린드롬으로 만들기 위해 필요한 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열이 주어진다. 영어 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력

첫째 줄에 문제의 정답을 출력한다.

Solution

입력 구현

1
2
import sys
s = sys.stdin.readline().rstrip()

문자열 교환 함수 구현

1
2
3
4
5
def swap(s, idx1, idx2):
  tmp = s[idx2]
  s = s[:idx2] + s[idx1] + s[idx2 + 1:]
  s = s[:idx1] + tmp + s[idx1 + 1:]
  return s

팰린드롬 공장 함수 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def Palindrome(s, idx1, idx2):
  if cache[idx1][idx2] != -1:
    return cache[idx1][idx2]
  while idx1 < idx2:
    if s[idx1] == s[idx2]:
      idx1 += 1
      idx2 -= 1
    else:
      break
  if idx1 >= idx2:
    return 0
  res = min(Palindrome(s, idx1 + 1, idx2) + 1, Palindrome(s, idx1, idx2 - 1) + 1, Palindrome(s, idx1 + 1, idx2 - 1) + 1)
  cache[idx1][idx2] = res
  return res
  • 길이가 51 $\times$ 51인 cache 변수에 대해 idx1, idx2가 초기값 -1이 아닌 경우 결과값 출력
  • 지정된 인덱스 idx1과 idx2으로부터 중앙 방향으로 펠린드롬 규칙을 만족할 경우 이동 후 만족하지 않을 때 정지
  • 삽입과 삭제를 idx1 + 1 혹은 idx2 - 1로 구현하고 교환은 idx1 + 1과 idx2 - 1로 구현
  • 세가지 중 가장 작은 값 출력

문자열 교환 고려 결과 출력

1
2
3
4
5
6
7
8
9
10
11
12
from itertools import combinations

l = len(s)
com = list(combinations([i for i in range(l)], 2))
ans = sys.maxsize
cache = [[-1 for _ in range(51)] for _ in range(51)]
ans = min(ans, Palindrome(s, 0, l - 1))
for c1, c2 in com:
  cache = [[-1 for _ in range(51)] for _ in range(51)]
  tmps = swap(s, c1, c2)
  ans = min(ans, Palindrome(tmps, 0, l - 1) + 1)
print(ans)
  • 조합과 문자열 교환 함수 swap()을 통해 4번 연산 후 가장 작은 값 출력