2193. Minimum Number of Moves to Make Palindrome

[zeikar]

Problem link

https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/

Problem Summary

주어진 문자열에서 최소한의 swap으로 팰린드롬을 만드는 문제.

Solution

이런류는 처음에 딱 보면 안떠오른다.

다시 잘 생각해보니 그리디로 될 것 같다.
앞에서부터 탐색하면서 팰린드롬이 되도록 중간에 있는 문자를 뒤로 옮긴다고 보면 된다.

예를 들면 ab....a...b 이런식이라고 하면 맨 앞의 a가 매치되도록 뒤의 a를 맨 뒤로 옮기면 된다. ab ...... ba 가 된다.
물론 반대로 b를 맨 앞으로 당길 수 있겠지만 어차피 a가 매치되도록 또 옮겨야 하므로 같다.

하나 예외사항이 글자가 하나인 경우인데, 이 글자는 무조건 가운데로 넣어야 한다. (문제에서 팰린드롬이 안되는 경우는 없다고 했으므로)
이거는 좀 까다로웠는데 그냥 가운데로 넣었다고 가정하고 문자열에서 제거해버려도 되고, 한칸씩 옮기는 것처럼 구현해도 된다.
(문자열에서 빼버리는 방법은...증명... 못하겠다)

아래 코드를 더 간결하게 한건lee 형님이 짜놓았다

Source Code

class Solution:
    def minMovesToMakePalindrome(self, s: str) -> int:
        s = list(s)

        result = 0
        i = 0
        while i < len(s) // 2:
            target = s[i]

            last = len(s) - i - 1
            j = last
            while j > i:
                if s[j] == target:
                    break
                j -= 1

            # move s[i] to len(s)//2
            if i == j:
                s.pop(i)
                result += len(s) // 2 - j
                continue

            for k in range(j, last):
                s[k], s[k + 1] = s[k + 1], s[k]

            result += last - j
            i += 1

        return result