[LeetCode] 1531. String Compression II

https://leetcode.com/problems/string-compression-ii/description/

leetcode - String Compression II

문제 유형 : 부분합, 다이나믹 프로그래밍, 재귀

문제 난이도 : Hard

 

 

문제

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은 연속되는 문자를 횟수로 대체하는 문자열 압축 메서드이다.

예를 들어서, 문자열 "aabccc"는 "a2bc3"으로 변환된다. 한 번 반복된 경우는 1을 추가하지 않는다.

 

문자열 s와 정수 k가 주어진다.

당신은 k개의 문자를 제거해야 한다.

Run-length encoding이 된 문자열의 길이가 최소가 되도록 하고, 그 길이를 구하시오.

 

 

풀이

탑-다운 방식의 재귀 다이나믹 프로그래밍으로 해결한다.

메모이제이션으로 하위 케이스들의 값들을 기반으로 문제를 해결한다.

 

dp[삭제가 허용되는 인덱스 시작점][남은 삭제 수] = RLE 압축된 문자열의 최소길이

의 형태로 저장시킨다.

문자열의 길이가 100까지이므로 101칸을 만들어주자.

 

재귀를 통해서 문제를 해결할 수 있다.

매개변수로 문자열 s, 삭제 시작 인덱스 idx, 남은 삭제 수 left를 사용한다.

 

===

만약 dp테이블에 이미 저장되어 있다면 반환해주면 되고,

유효하지 않은 경우(남은 수(전체 문자열 길이 - 시작 인덱스)가 남은 삭제 수보다 작거나 같은 경우), 0을 반환한다.

 

1. 현재 인덱스를 제거한 경우에서 최소길이 구하기
2. 압축된 문자열의 길이를 구함.
   • 다음 인덱스부터 끝까지의 부분문자열마다 각각 남은 삭제량만큼 삭제한 값의 최소 길이를 구하고, 그에 따라서 최소값 갱신

 

dp테이블에 최소값을 담고 그 값을 반환.

 

===

 

코드

C++

class Solution {
public:
    int dp[101][101];

    int solve(string &s, int idx, int left) {
        const int n = s.size();
        int k = left;
        if(n-idx <= k) return 0;
        if(dp[idx][k] != -1) return dp[idx][k];

		// 현재 인덱스를 없앤 경우에서의 최소 RLE길이 구하기
        int result = left? solve(s, idx+1, k-1) : 101, c = 1;

        for(int i = idx + 1; i <= n; i++) {
        	// 최소값 업데이트
            result = min(result, 1+((c>99)?3:(c>9)?2:(c>1)?1:0) + solve(s, i, k));
			
            // 만약 문자가 계속 일치한다면, 쭉 이어가기
            if(i < n && s[idx] == s[i]) c++;
            // 아니라면, 다음 반복문에서 문자 제거 시도. 더 없앨 문자열이 없다면 그만두기
            else if(--k < 0) break;
        }
        // 테이블에 저장하고 반환
        return dp[idx][left] = result;
    }

    int getLengthOfOptimalCompression(string s, int k) {
        memset(dp, -1, sizeof(dp));
        return solve(s, 0, k);
    }
};