Computer >> 컴퓨터 >  >> 프로그래밍 >> JavaScript

JavaScript로 문자열 인코딩하기: 반복 패턴 압축으로 크기 줄이기

문제 정의

문자열 str을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 입력받은 문자열을 특정 규칙에 따라 인코딩한 뒤, 그 결과의 길이와 원본 문자열의 길이를 비교하여 더 짧은 쪽을 반환해야 합니다.

인코딩 규칙

문자열을 인코딩하는 규칙은 다음과 같습니다.

  • n[s] 형태로 표현하며, 대괄호 안의 문자열 s가 정확히 n번 반복된다는 의미입니다.

예를 들어 ddd는 3[d]로 인코딩할 수 있습니다. 하지만 3[d]는 길이가 4인 반면 원본 ddd는 길이가 3에 불과합니다. 따라서 이 경우에는 인코딩하지 않고 원본 문자열 ddd를 그대로 반환하는 것이 맞습니다.

입력 및 출력 예시

함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

const str = 'aabcaabcd';

이때 기대되는 출력 결과는 다음과 같습니다.

const output = '2[aabc]d';

aabcaabc 부분이 2[aabc]로 압축되어 전체 문자열이 더 짧아진 것을 확인할 수 있습니다.

풀이 접근 방식: 동적 계획법(DP)

이 문제는 구간별 최적 해를 활용하는 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • dp[i][j]는 부분 문자열 s[i..j]를 인코딩했을 때 얻을 수 있는 가장 짧은 결과를 저장합니다.
  • 구간 길이를 1부터 전체 길이까지 순차적으로 늘려가며, 작은 구간들의 최적 결과를 조합해 더 큰 구간의 최적 결과를 만듭니다.
  • 각 구간에 대해 두 가지 경우를 고려합니다. 첫째, 인접한 두 하위 구간의 인코딩 결과를 이어 붙이는 방식입니다. 둘째, 해당 구간이 어떤 패턴의 반복이라면 n[패턴] 형태로 압축하는 방식입니다.
  • 반복 여부는 부분 문자열을 자기 자신과 한 번 더 이어 붙인 뒤, 첫 번째 위치 이후에서 다시 자기 자신이 등장하는지 검사하여 확인합니다.

구현 코드

const str = 'aabcaabcd';

function encode(s) {
    const { length } = s;
    const dp = Array(length).fill([]);
    dp.forEach((el, ind) => {
        dp[ind] = Array(length).fill(null);
    });
    for(let l = 1; l <= length; l++){
        for(let i = 0; i + l <= length; i++){
            let j = i + l - 1;
            dp[i][j] = s.substring(i, j + 1);
            for (let k = i; k < j ; k ++) {
                let acc = dp[i][k] + dp[k + 1][j];
                if (acc.length < dp[i][j].length) {
                    dp[i][j] = acc;
                }
            }
            let sub = s.substring(i, j + 1);
            let double = sub + sub;
            let cut = double.indexOf(sub, 1);
            if (cut != -1 && cut < sub.length) {
                let acc = sub.length / cut + "[" + dp[i][i + cut - 1] +"]";
                if (acc.length < dp[i][j].length) {
                    dp[i][j] = acc;
                }
            }
        }
    }
    let res = dp[0][dp.length - 1];
    return res;
}
console.log(encode(str));

코드 설명

코드의 주요 흐름을 단계별로 살펴보면 다음과 같습니다.

  1. DP 테이블 초기화: 문자열 길이만큼의 2차원 배열을 만들어 각 구간의 최적 인코딩 결과를 저장할 공간을 마련합니다.
  2. 구간 길이 확장: 길이 1부터 시작해 전체 문자열까지 모든 구간을 순회하며 dp[i][j]를 채워 나갑니다.
  3. 분할 조합: 구간 내 분할 지점 k를 옮겨가며 좌측과 우측의 인코딩 결과를 연결했을 때 더 짧아지는지 확인합니다.
  4. 반복 패턴 압축: 구간이 완전히 반복되는 패턴이라면 반복횟수[패턴] 형태로 변환하고, 그 결과가 더 짧을 때만 채택합니다.
  5. 최종 결과 반환: dp[0][length - 1], 즉 전체 문자열에 대한 최적 인코딩 결과를 반환합니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

2[aabc]d

원본 문자열 aabcaabcd(9자)가 2[aabc]d(8자)로 줄어들었으므로, 함수는 압축된 인코딩 결과를 올바르게 반환합니다. 만약 인코딩 결과가 원본보다 길거나 같다면 원본 문자열이 그대로 반환됩니다.