Leetcode 1531. String Compression II

문제

Run-length encoding is a string compression method 
that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character 
and the number marking the count of the characters (length of the run). 
For example, to compress the string "aabccc" we replace "aa" by "a2" and replace "ccc" by "c3". 
Thus the compressed string becomes "a2bc3".

Notice that in this problem, we are not adding '1' after single characters.

Given a string s and an integer k. 
You need to delete at most k characters from s such that the run-length encoded version of s 
has minimum length.

Find the minimum length of the run-length encoded version of s after deleting at most k characters.

Run-length encoding 은 문자열을 압축하는 방식중 하나로, 문자가 연속해서 2개 이상 등장할시 이를 (해당문자열)(문자열이 등장한 횟수)
로 표현하는 것으로, 예를 들어 aaabbcccc 는 a3b2c3 으로 표현할수 있다.
주어진 문자열 s를 Run-length encoding 으로 압축하되, 최대 k개의 문자를 s로부터 제거할수 있을때,
제거 후 Run-length encoding 을 돌렸을때 나올수 있는 가장 짧은 결과물의 길이를 리턴하시오.

예시

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: b와 d를 제거하면 a3c3이 된다.

제한

• $1 <= s.length <= 100$
• $0 <= k <= s.length$
• 문자열은 소문자만 포함한다.

풀이법

연속된 문자열을 삭제할때

• 연속된 문자열에 대해 중간에서부터 삭제하던 연속된 문자열의 첫부분에서부터 삭제하던 결과는 변함이 없다.
• 즉, 연속된 문자열의 중간부분은 삭제하지 않는다.

위 경우를 고려했을때 문자를 삭제하는 경우는 다음과 같다.

1. 연속된 문자열의 중간
   • 해당 문자를 삭제하지 않는다.
2. 문자가 다른문자로 바뀌었을때
   • 그 문자를 삭제한다.
   • 그 문자를 삭제하지 않는다.

• 이들을 cache로 memoization 해 계산한다.
  정확한 설명은 아래 코드에 주석으로 표기하겠다.

class Solution:
    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        cache = {}
		
        
      	'''
       	i : 현재 확인할 문자열의 부분
        k : 현재까지 삭제한 문자 수
        prev : 바로 직전의 문자
        prev_count : 바로 직전의 문자가 몇번 반복되었는지 횟수
        '''
        def count(i: int, k: int, prev: str, prev_count: int):
			# 이전에 계산 된 결과일시 가져와 바로 보낸다.
            if (i, k, prev, prev_count) in cache:
                return cache[(i, k, prev, prev_count)]

			# 만약 k가 0보다 작다는것은 정해진 횟수보다 많이 삭제되었다는 뜻이기에
            # 절대 답이 될수 없는 수 ( 매우 큰 수 ) 를 리턴한다.
            if k < 0:
                return 99999
                
            # 끝까지 확인이 끝났다면 0을 리턴한다.
            if i == len(s):
                return 0

            if s[i] == prev:
            # 반복되는 문자열의 중간에 위치한다.
            # increment는 문자가 1번 반복에서 2번 반복이 될때 뒤에 숫자가 붙는것
            # 9 -> 10, 99 -> 100 번 반복이 될때마다 Encoding시 길이가 1씩 증가하는것을 추가하기 위함이다.
                increment = 1 if prev_count in [1, 9, 99] else 0
                res = increment + count(i+1, k, prev, prev_count+1)
            else:
                res = min(
                # s[i]가 삭제할때를 의미한다, 삭제 가능한 양인 k를 1 줄이고, i번째가 삭제되니 나머지는 유지된다.
                    count(i+1, k-1, prev, prev_count),
                # s[i]가 삭제되지 않을때를 의미한다, 새로운 문자가 왔기에 prev를 s[i]로 바꾸고 길이를 1로 바꾼다.
                    1 + count(i+1, k, s[i], 1)
                )
			
            # 계산 완료시 cache 에 memoization 한다.
            cache[(i, k, prev, prev_count)] = res

            return res
		
        # 0번째부터 확인하고, k개를 삭제할수 있되, 이전 문자열은 존재하지 않고, 0번 반복되었다.
        return count(0, k, "", 0)