664. Strange Printer

[zeikar]

Problem link

https://leetcode.com/problems/strange-printer/

Problem Summary

한 문자를 죽 이어 붙이거나 특정 범위의 문자열을 교체하는 2가지 연산을 할 때 최소한의 연산으로 문자열을 만드는 횟수를 찾는 문제.

Solution

약간 분할 정복, 완전탐색 느낌이 나는데 쉽지 않다.

일단 양옆이 같은 문자인 경우 중간을 바꿔치기 했다고 생각할 수 있다. 그 외의 경우는 이어 붙여야 한다.
따라서 문제를 나눠볼 수 있는데 맨 앞과 같은 문자가 중간에 나온 경우 처음부터 거기까지를 나누고 그 다음부분으로 나눌 수 있다.
그 외의 경우 그냥 무식하게 붙이는 수밖에 없다.

인덱스로 cache를 하면 (시작과 끝 인덱스) 공간복잡도를 줄일 수 있지만 가독성은 이게 좋으므로 이렇게 놔두었다.

뭔가 잘 돌아가는데 왜 잘 돌아가는지 모르겠다...

Source Code

class Solution:
    def strangePrinter(self, s: str) -> int:

        @cache
        def dfs(s):
            if len(s) == 0:
                return 0

            ret = 1 + dfs(s[1:])

            for i in range(1, len(s)):
                if s[i] == s[0]:
                    ret = min(ret, dfs(s[1:i]) + dfs(s[i:]))

            return ret

        return dfs(s)