[코테] 문자열 압축하는 방법

✨문제 설명

문자열을 압축하는 방법 |

정해진 길이로 문자열을 압축했을 때, 압축된 문자열의 수를 앞에 써주고, 뒤에 해당 문자열이 오도록 배치합니다. 예시로 `aabbccc`라는 문자열은 1의 길이로 압축했을 때, `2a2b3c`가 되며, 2의 길이로 압축했을 때 `aabbccc` 로 압축횟수가 1인 경우 생략하여 표기합니다. 따라서 이번 입력값의 압축 시 최소 길이는 6입니다.

파라미터 |  압축할 문자열 s

조건 | 

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

리턴값 | 압축한 문자열 중 가장 짧은 길이

 

🤔풀이 방법

1. 문자열을 자르는 길이가 일정하므로, 해당 길이만큼 문자열을 미리 잘라놓는 방법

> split 메서드를 통해 문자열을 일정 길이로 잘라 배열로 반환할 수 있습니다.

다만, 문자열이 일정 길이만큼 반복되지 않습니다. 즉, `abcabc`의 경우 3번 반복되지만, `aabcabc`의 경우 앞의 a로 인해 문자열이 원하는대로 잘리기 어렵습니다. split을 쓴 결과로 [`a`, ``, ``]가 되면 좋지만, [``, ``, `bc, ``, `bc`]가 될 수도 있습니다. 따라서 이 방법은 이 문제에 적합하지 않아 아래 방법을 사용하였습니다.

2. 문자열을 앞에서부터 길이만큼 하나씩 잘라가며 뒤의 문자열과 비교하는 방법

사용한 메서드 | slice(시작인덱스, 마지막인덱스+1), Math.min(숫자들)

사용한 자료구조 | 스택

풀이 코드 | 

function solution(s) {
    const stack = [];
    const length = s.length;
    const answer = [s];
    let currentAnswer = 0;
    for(let n = 1; n < length/2 + 1; n++){
        currentAnswer++;
        answer[currentAnswer] = '';
        for(let i = 0; i < length; i++){
            const value = s.slice(i * n, i * n + n);
            const next = s.slice((i+1) * n, (i+1) * n + n ) ?? value;
            if(value === next){
                stack.push(value);
            }else{
                const pressCount = press(stack);
                pressCount > 1 ? answer[currentAnswer] += pressCount + value : answer[currentAnswer] += value;
            }
        }
    }
    const answerLength = answer.map(e => e.length);
    
    return Math.min(...answerLength);
}

function press(stack) {
    let pressCount = 1;
    while(stack.pop()){
        pressCount++;
    }
    return pressCount;
}

변수 설명 |

• answer : 압축한 문자열을 담는 배열
• curruentAnswer : 현재 압축중인 문자열이 있는 곳을 가리키는 인덱스
• answerLength : answer의 각 요소들의 길이를 담는 배열
• stack : n개씩 자른 문자열이 들어가는 배열
• length : s 문자열의 총 길이
• value : 기준이 되는 문자열
• next : 비교할 다음 문자열
• pressCount : 압축한 횟수

 

코드 설명 |

문자열 압축시 최대 압축 가능한 것은 `문자열 길이의 1/2 + 1`에 해당합니다.
즉, 1 ~ `문자열길이의 1/2 + 1`까지 압축해보고 가장 길이가 짧은 것을 반환합니다.
> 여기에서 +1을 해도 되며, Math.ceil()을 사용하여 올림처리해도 가능합니다.

n개 단위로 문자열을 자르므로,

1. 0~n-1번째 문자열을 스택에 push
2. 다음 n ~ 2n-1번째 문자열을 비교
3. 같으면 스택에 push.
4. 다를 경우 스택에 pop.
   1. 스택에서 pop한 횟수 === 압축횟수
   2. 압축횟수가 1일 경우, 무시하고 문자열만 저장
   3. 압축횟수가 1 초과일 경우, 압축횟수+마지막 pop한 문자열 저장
   4. 새로운 문자열을 스택에 push

즉, 스택에 push === 같은 문자열 ➡️ 문자열 비교 범위 이동
스택에 pop === 다른 문자열 ➡️ 압축 로직 실행 ➡️ 문자열 비교 범위 이동

📜생각

제출한 답안지의 주석으로만 남아있을 내용들을 정리해보았습니다. 그리고 이 문제에 2시간을 쏟을 만큼 그동안 문제를 안 풀긴 했구나라는 걸 느꼈습니다. 앞으로도 기억에 남는 문제들과 관련 자료구조와 알고리즘들을 이렇게 정리해보려고 합니다.