1531. String Compression II

• 현재 문자열을 추가하는 경우, 추가하지 않는 경우로 나누어 재귀 호출로 풀어보려고 했지만 실패.
• 시간 초과 + 오답

• 문자열의 앞쪽 부터 일부분을 취하여 해당 문자열에서 최대 k 개 만큼의 문자열을 삭제한다고 했을 때 encoding 된 길이를 차례대로 구한다.

• 앞부분 부터 특정 길이 len로 자른 문자열에 대하여 del 개의 문자열을 삭제했을 때 encoding 된 길이를 구한다.
• 먼저 가장 쉬운 케이스는 현재 문자열을 삭제하는 경우이다.
• 현재 문자열을 삭제한다면 그 값은 이전 길이 len - 1에서 문자열을 하나 덜 삭제한 경우 del - 1와 동일한 encoding 길이를 가진다 (왜냐하면 더하는 문자열이 없기 때문에).
• 따라서 값은 dp[len - 1][del - 1]를 그대로 쓴다.
• 그 다음은 현재 문자열의 가장 마지막 문자 lastChar을 기준으로 동일한 문자열은 남기고 나머지는 삭제하는 경우이다 (제일 이해하기 어려웠던 부분).
• 마지막 문자열부터 역순으로 순회하면서 매 index l 마다 마지막 문자 lastChar와 동일한 문자의 수 (남길 것) addCount와 동일하지 않은 문자의 수 (삭제할 것) delCount를 센다.
• 특정 index l을 기준으로 [0, len) 구간을 두개로 나눈다 [0, l), [l, len).
• (중요!!) 두 구간에서 삭제한 문자의 숫자가 del이 되도록 만든다.
• 뒷쪽 부분 [l, len)은 addCount 만큼의 문자열을 encoding 한 길이가 결과 값이 된다.
• 앞쪽 부분은 나머지 남은 삭제 문자 수를 채울 수 있도록 앞서 계산된 구간 [0, l)의 결과 중 del - delCount의 삭제 문자 숫자를 가진 것 dp[i][del - delCount]을 취한다.

class Solution {
    int getCodedLength(int count) {
        if (count <= 1) return 1;
        int length = 1;
        while (count > 0) {
            ++length;
            count /= 10;
        }
        return length;
    }

    public int getLengthOfOptimalCompression(String s, int k) {
        int n = s.length();
        // (sub string length, deleted character count)
        int[][] dp = new int[n + 1][k + 1];
        for (int[] sub : dp) {
            // fill with maximum + 1 value
            Arrays.fill(sub, n + 1);
        }
        // zero length
        dp[0][0] = 0;
        for (int len = 1; len <= n; ++len) {
            char lastChar = s.charAt(len - 1);
            for (int del = 0; del <= k; ++del) {
                int addCount = 0, delCount = 0;
                for (int i = len - 1; i >= 0; --i) {
                    if (s.charAt(i) == lastChar)
                        ++addCount;
                    else
                        ++delCount;
                    
                    if (del - delCount >= 0) {
                        // get result of sub string [0, i) 
                        // and add characters in sub string [i, len)
                        int newValue = dp[i][del - delCount] + getCodedLength(addCount);
                        dp[len][del] = Math.min(
                            dp[len][del], newValue);
                    }
                }
                if (del > 0) {
                    // remove current character
                    dp[len][del] = Math.min(
                        dp[len][del], dp[len - 1][del - 1]);
                }
            }
        }
        return dp[n][k];
    }
}