[프로그래머스 카카오블라인드] 문자열 압축

프로그래머스

 

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

 

첫번째 풀이

로직

단위 크기별로 잘라서 만든 모든 문자열들을 구한뒤 sort해서 가장 짧은 걸 구한다.

 

최대로 긴 단위는 문자열의 반 절 길이므로 그 만큼만의 단축 문자열을 구하면 된다

for (let i = 1; i <= Math.floor(문자길이 / 2) ; i++)

prev에 맨 처음 조각을 주고 curr에 그 다음 조각을 준다 

prev, curr가 같은면 prev의 횟수를 늘려주고 결과 문자열 totalStr을 변경해준다

prev, curr가 다르면 prev를 curr로 변경하고 totalStr + curr

 

위 과정을 while로 모든 문자를 단축할때까지 돌린다.

 

splice

array.splice(start, deleteCount [, item1 [, item2 [, ...] ] ])

start: 시작하는 index를 지정

deleteCount: start index부터 몇 개의 요소를 제거할지 지정

item.. : 삽입할 요소

 

리턴: 제거한 요소들의 배열을 반환을 리턴한다

splice로 중간에 삽입하기

array.splice(시작 인덱스, 0, 삽입할 것);

const a = [1,2,3];
a.splice(1, 0, 4); 1번 인덱스로 4를 삽입
console.log(a) // [1, 4, 2, 3]

 

 

전체코드

// 짧게 만든걸 구하고 sort
function isSame(a, b) {
    for (let i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) {
            return false
        }
    }
    return true;
}

function solution(s) {
    var answer = 0;
    const strings = [s];
    
    // 최대 문자열 단위는 Math.floor(s.length/2)
    for (let unit = 1; unit <= Math.floor(s.length/2); unit++) {
        let rest = [...s];
        let prev = {
            str: rest.splice(0, unit).join(''),  // join
            count: 1,
        };
        let totalStr = prev.str;
        
        while(rest.length) {
            const curr = rest.splice(0, unit).join('');
            // 전과 같을 때
            if (isSame(prev.str, curr)) {
                const newTotalStr = [...totalStr]; // splice는 반환
                // 전에 1개 였을때
                if (prev.count === 1) {
                    prev.count += 1;
                    newTotalStr.splice(totalStr.length-curr.length, 0, prev.count);
                    totalStr = newTotalStr.join('');
                }
                // 2개 이상일때
                else if (prev.count > 1) {
                    prev.count += 1;
                    newTotalStr.splice(totalStr.length- curr.length-1, 1, prev.count);
                    totalStr = newTotalStr.join('');
                }
            }
            // 전과 다를 때
            else {
                prev.str = curr;
                prev.count = 1;
                totalStr += curr;
            }
        }
        strings.push(totalStr);
    }
    return strings.sort((a, b) => a.length - b.length)[0].length;
}

 

 

 

두번째 풀이

중복되는 문자의 개수가 2자리 이상인 경우

전의 문자가 반복된 갯수가 10같이 2자리면 splice할때 인덱스의 값을 2자리로 해줘야한다

예를 들어 2a이면 splice(0, 1, 2+1)로 3a로 변경이 가능하지만,

10a이면 splice(0, 2, 10+1) 로 계산해서 11a로 변경해야한다

 

=> 전 문자의 갯수의 digit을 구해서 그만큼 교체해줘야함

// 2개 이상일때
else if (prev.count > 1) {
    const prevCountDigit = String(prev.count).length; // 전에 문자의 자릿수 만큼 교체
    prev.count += 1; //
    newTotalStr.splice(totalStr.length - curr.length - prevCountDigit, prevCountDigit, prev.count); // 교체
    totalStr = newTotalStr.join('');
}

 

주의

• 숫자의 자릿수digit = 숫자를 문자열로 변경한뒤 문자열의 길이 String(숫자).length
• splice().join()
• 삽입: splice(시작, 0개, 삽입할 것)
• 교체: splice(시작, 교체할 갯수, 교체할 것)

// (X)
const 제거한것들배열 = 배열.splice();

// (O)
const 새로운배열 = [...원래 배열];
새로운배열.splice();

 

추가 테케

 

 

 

두번째 풀이

// 짧게 만든걸 구하고 sort
function isSame(a, b) {
    for (let i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) {
            return false
        }
    }
    return true;
}

function solution(s) {
    var answer = 0;
    const strings = [s];
    
    // 최대 문자열 단위는 Math.floor(s.length/2)
    for (let unit = 1; unit <= Math.floor(s.length/2); unit++) {
        let rest = [...s];
        let prev = {
            str: rest.splice(0, unit).join(''),  // join
            count: 1,
        };
        let totalStr = prev.str;
        
        while(rest.length) {
            const curr = rest.splice(0, unit).join('');
            // 전과 같을 때
            if (isSame(prev.str, curr)) {
                const newTotalStr = [...totalStr]; // splice는 반환
                // 전에 1개 였을때
                if (prev.count === 1) {
                    prev.count += 1;
                    newTotalStr.splice(totalStr.length-curr.length, 0, prev.count); // 삽입
                    totalStr = newTotalStr.join('');
                }
                // 2개 이상일때
                else if (prev.count > 1) {
                    const prevCountDigit = String(prev.count).length; // 전에 문자의 자릿수 만큼 교체
                    prev.count += 1; //
                    newTotalStr.splice(totalStr.length - curr.length - prevCountDigit, prevCountDigit, prev.count); // 교체
                    totalStr = newTotalStr.join('');
                }
            }
            // 전과 다를 때
            else {
                prev.str = curr;
                prev.count = 1;
                totalStr += curr;
            }
        }
        strings.push(totalStr);
    }
    return strings.sort((a, b) => a.length - b.length)[0].length;
}