문자열 압축

🔒 문제

💭 생각의 흐름

1자리 2자리 3자리.. n / 2 자리의 패턴 매칭갯수 결과중 가장 최소길이를 산출 했을 시의 길이를 구한다.

🧠 2/n 자리 이상은 의미가 없다. ex) abcdefabcdf 총 10자리에서 6자리 패턴은 2번째 검사시 자릿수 부족으로 검사되지 않는다.

∴ 전체 길이 / 2 만큼까지의 패턴만 검사해본다.

⚠️ 실수

(1) number 형은 integer가 아니다..
ex) 9 / 2 == 4.5 이다.. c++, kotlin에서 int, Int 형은 당연히 4였건만..

자동으로 소수점 계산까지 되기 때문에 Math.floor 메소드로 버림처리를 해주어야한다.

(2) patternCount가 10 이상일 경우 앞 정수가 2자리 이상 차지하기 때문에
10 -> 2자리, 100 -> 3자리 ,, 자릿수에 따라 차감되는 경우가 다르다.
나같은 경우 1자리로만 차감해서 일부 케이스를 통과하지 못했었다.

😵 비효율적인 풀이 (build Heap)

function getCompressedLength(s: string, unit: number): number {
    // 압축된 문자열 길이만큼 다음 단위에서 같은 패턴이 등장할 경우 압축 성공.
    let compressedLength : number = s.length;
    let patternCount = 0;

    for (let index = 0; index < s.length - unit; index += unit) {
        while (index < s.length - unit && s.substr(index, unit) === s.substr(index + unit, unit)) {
            patternCount++;
            index += unit;
        }

        compressedLength -= (patternCount === 0) ? 0 : (unit * patternCount - 1);
        patternCount = 0;
    }

    return compressedLength;
}

const getLeftChildIndex = (index : number)=> index * 2 + 1;
const getRightChildIndex = (index : number) => index * 2 + 2;
const getMinValue = (arr : number[]) => arr[0];

function buildMinHeap(arr: number[]) : void {
    const rootIndex : number = 0;
    for (let index = Math.floor(arr.length - 1 / 2); index >= rootIndex; index--) {
        shiftDown(arr, index);
    }
}


function shiftDown(arr: number[], index: number) : void {

    let lesserIndex : number = index;

    while (index < arr.length) {
        const leftChildIndex : number = getLeftChildIndex(index);
        const rightChildIndex : number = getRightChildIndex(index);

        if (leftChildIndex < arr.length && arr[index] > arr[leftChildIndex]) lesserIndex = leftChildIndex;
        if (rightChildIndex < arr.length && arr[lesserIndex] > arr[rightChildIndex]) lesserIndex = rightChildIndex;

        if (index === lesserIndex) break;
        [arr[index], arr[lesserIndex]] = [arr[lesserIndex], arr[index]]; // swapping

        index = lesserIndex;
    }
}

function solution(s : string) : number {
    const stringLength : number = s.length;
    const arr : number[] = [];

    for (let unit : number = 1; unit <= Math.floor(stringLength / 2) ; unit++) {
        arr.push(getCompressedLength(s, unit));
    }


    buildMinHeap(arr);

    return getMinValue(arr);
}

console.assert(solution("aabbaccc") === 7);
console.assert(solution("ababcdcdababcdcd") === 9);
console.assert(solution("abcabcdede") === 8);
console.assert(solution("abcabcabcabcdededededede") === 14);
console.assert(solution("xababcdcdababcdcd") === 17);

minHeap을 만들 필요가 없다. O(2N)이 걸리는데, 사실 최소값만 구하면 되기 때문에 O(N)에 처리할 수 있는 문제다.

풀이2

// pattern Count 늘어날 때 2자리 이상되면 자릿수 늘어남.
function getCompressedLength(s: string, unit: number): number {
    // 압축된 문자열 길이만큼 다음 단위에서 같은 패턴이 등장할 경우 압축 성공.
    let compressedLength : number = s.length;
    let patternCount = 0;

    for (let index = 0; index < s.length - unit; index += unit) {
        while (index < s.length - unit && s.substr(index, unit) === s.substr(index + unit, unit)) {
            patternCount++;
            index += unit;
        }

        compressedLength -= (patternCount === 0) ? 0 : (unit * patternCount - patternCount.toString().length);
        patternCount = 0;
    }

    return compressedLength;
}

function solution(s : string) : number {
    const stringLength : number = s.length;
    let answer : number = s.length;

    for (let unit : number = 1; unit <= Math.floor(stringLength / 2) ; unit++) {
        const compressedLength = getCompressedLength(s, unit)
        answer = (answer > compressedLength) ? compressedLength : answer;
    }

    return answer;
}

console.log(solution("aaaaaaaaaab"));

// console.assert(solution("aabbaccc") === 7);
// console.assert(solution("ababcdcdababcdcd") === 9);
// console.assert(solution("abcabcdede") === 8);
// console.assert(solution("abcabcabcabcdededededede") === 14);
// console.assert(solution("xababcdcdababcdcd") === 17);
console.assert(solution("aaaaaaaaaab") === 4);

patternCount 2자리 이상일 때를 고려하지 않은 계산식

        compressedLength -= (patternCount === 0) ? 0 : (unit * patternCount - patternCount.toString().length);

🔑 정답 풀이 (Javascript)

"use strict";
// pattern Count 늘어날 때 2자리 이상되면 자릿수 늘어남.
function getCompressedLength(s, unit) {
    // 압축된 문자열 길이만큼 다음 단위에서 같은 패턴이 등장할 경우 압축 성공.
    let compressedLength = s.length;
    let patternCount = 1;
    for (let index = 0; index < s.length - unit; index += unit) {
        while (index < s.length - unit && s.substr(index, unit) === s.substr(index + unit, unit)) {
            patternCount++;
            index += unit;
        }
        compressedLength -= (patternCount === 1) ? 0 : (unit * (patternCount - 1) - patternCount.toString().length);
        patternCount = 1;
    }
    return compressedLength;
}

function solution(s) {
    const stringLength = s.length;
    let answer = s.length;
    for (let unit = 1; unit <= Math.floor(stringLength / 2); unit++) {
        const compressedLength = getCompressedLength(s, unit);
        if (answer > compressedLength) answer = compressedLength;
    }
    
    return answer;
}

O(N)으로 풀이 성공!