문제 개요
비어 있지 않은 문자열이 하나 주어졌을 때, 인코딩된 결과의 길이가 최소가 되도록 해당 문자열을 인코딩해야 합니다.
인코딩 규칙은 k[encoded_string] 형태입니다. 이는 대괄호 안의 encoded_string이 정확히 k번 반복된다는 의미입니다. 단, 다음 조건을 반드시 지켜야 합니다.
- k는 항상 양의 정수여야 합니다.
- 인코딩된 문자열은 비어 있으면 안 되며, 불필요한 공백을 포함해서도 안 됩니다.
- 입력 문자열에는 소문자만 포함되어 있다고 가정합니다.
만약 인코딩 과정을 거쳐도 문자열이 더 짧아지지 않는다면, 해당 문자열은 인코딩하지 않고 그대로 두어야 합니다.
예를 들어 입력이 "aaaaa"라면 출력은 "5[a]"가 됩니다. "5[a]"는 원래 문자열 "aaaaa"보다 1자 더 짧기 때문입니다.
해결 접근 방법
이 문제는 구간 DP(Interval DP) 기법으로 해결할 수 있습니다. 문자열의 모든 부분 구간에 대해 최적의 인코딩 결과를 바텀업 방식으로 계산하며, 각 구간마다 반복 패턴을 찾아 압축 가능한지 검사합니다.
구체적인 풀이 단계는 다음과 같습니다.
- 2차원 배열 dp를 정의합니다. dp[i][j]는 s의 i번째부터 j번째까지 부분 문자열의 최적 인코딩 결과를 저장합니다.
- collapse() 함수를 정의합니다. 이 함수는 s, i, j를 매개변수로 받습니다.
- temp := s의 인덱스 i부터 j까지의 부분 문자열
- x := temp와 temp를 연결한 문자열
- pos := x에서 temp가 처음으로 다시 나타나는 위치(반복 주기)
- pos가 temp의 크기보다 크거나 같으면 반복 패턴이 없으므로 temp를 그대로 반환합니다.
- 그렇지 않으면 (temp의 크기 ÷ pos)를 문자열로 변환한 뒤 '[', dp[i][i+pos-1], ']'를 차례로 연결하여 반환합니다.
- encode() 함수를 정의합니다. 이 함수는 s를 매개변수로 받습니다.
- n := s의 크기
- dp := n × n 크기의 2차원 배열 생성
- l := 1부터 l ≤ n까지 l을 1씩 증가시키며 반복:
- i := 0, j := l - 1부터 시작해 j < n인 동안 i와 j를 1씩 증가시키며 반복:
- dp[i][j] := s의 인덱스 i부터 j까지의 부분 문자열로 초기화
- k := i부터 k < j까지 k를 1씩 증가시키며 반복:
- temp := dp[i][k] + dp[k+1][j]
- temp의 길이가 dp[i][j]보다 짧으면 dp[i][j] := temp로 갱신
- rep := collapse(s, i, j) 호출
- rep의 길이가 dp[i][j]보다 짧거나 같으면 dp[i][j] := rep으로 갱신
- i := 0, j := l - 1부터 시작해 j < n인 동안 i와 j를 1씩 증가시키며 반복:
- 모든 반복이 끝나면 dp[0][n-1]을 반환합니다.
collapse() 함수에서 문자열을 자기 자신과 한 번 이어 붙인 뒤 원래 문자열이 다시 등장하는 위치를 찾는 것은, 클래식한 반복 주기 탐색 트릭입니다. 이를 통해 해당 구간이 어떤 패턴의 반복으로 이루어져 있는지 효율적으로 파악할 수 있습니다.
구현 예제
더 나은 이해를 위해 다음 C++ 구현 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<string>> dp;
string collapse(string &s, int i, int j) {
string temp = s.substr(i, j - i + 1);
string x = temp + temp;
auto pos = x.find(temp, 1);
if (pos >= temp.size())
return temp;
return to_string((temp.size() / pos)) + "[" + dp[i][i + pos - 1] + "]";
}
string encode(string s) {
int n = s.size();
dp = vector<vector<string>>(n, vector<string>(n, ""));
for (int l = 1; l <= n; l++) {
for (int i = 0, j = l - 1; j < n; i++, j++) {
dp[i][j] = s.substr(i, j - i + 1);
for (int k = i; k < j; k++) {
string temp = dp[i][k] + dp[k + 1][j];
if (temp.size() < dp[i][j].size()) {
dp[i][j] = temp;
}
}
string rep = collapse(s, i, j);
if (rep.size() <= dp[i][j].size()) {
dp[i][j] = rep;
}
}
}
return dp[0][n - 1];
}
};
main() {
Solution ob;
cout << (ob.encode("bbbbbbbbbb"));
}입력
"bbbbbbbbbb"
출력
"10[b]"
위 예제에서 길이 10의 문자열 "bbbbbbbbbb"는 "10[b]"로 인코딩되어 4자 더 짧아진 것을 확인할 수 있습니다. 시간 복잡도는 구간 DP의 세 겹 반복문과 문자열 연산에 의해 O(n⁴) 수준이며, n이 작은 경우에 실용적으로 동작합니다.