[프로그래머스 Level 2] 문자열 압축 - JavaScript

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

✏️ 풀이

function solution(s) {
    let compression = s;
    for (let i = 1; i <= Math.floor(s.length / 2); i++) {
        let target;
        let count = 0;
        const result = [];
        for (let j = 0; j < s.length; j += i) {
            const matched = s.slice(j, j + i);
            if (!target) {
                target = matched;
                count = 1;
            } else {
                if (matched === target) {
                    count++;
                } else {
                    result.push(count > 1 ? `${count}${target}` : target);
                    target = matched;
                    count = 1;
                }
            }
        }
        result.push(count > 1 ? `${count}${target}` : target);
        const curCompression = result.join('');
        if (compression.length > curCompression.length) {
            compression = curCompression;
        }
    }
    return compression.length;
}

문자열을 자르는 단위를 1개부터 시작해서 점점 개수를 늘려나가면서 모든 가능한 경우를 확인해보았다.

여기서 문자열을 s의 길이의 1/2보다 길게 자르는 것은 의미가 없기 때문에 (s.length / 2)까지만 확인하였다.

 

target에는 현재 찾고 있는 문자열을, count에는 target 문자열이 현재 연속으로 몇 개째 나오고 있는지를, 그리고 result에는 문자열을 순회하면서 압축한 부분 문자열들을 저장하도록 하였다.

 

문자열 s를 i개 단위로 순회한다.

첫 순회일 때는 target을 현재 순회중인 문자열로 갱신하고 count를 1로 초기화한다.

그 다음부터는 target에 있는 문자열과 현재 순회중인 문자열이 일치하는지 확인한다.

일치하면 count를 증가시키고, 일치하지 않으면 result에 압축 결과를 저장하고 다시 target을 현재 순회중인 문자열로 갱신하고 count를 1로 초기화한다.

 

이렇게 해서 문자열 s를 한 번 순회하고 나면 마지막으로 순회했던 문자열의 압축 결과가 아직 result에 담기지 않았으므로 for문이 끝나고 result에 마지막으로 순회했던 문자열의 압축 결과를 저장한다.

그리고 이 압축된 문자열들을 이어서 완성된 하나의 문자열을 만들면 i개 단위로 잘랐을 때의 문자열 압축 결과가 된다.

이 압축 결과를 매 번 비교하여 가장 짧은 길이의 압축 결과를 compression에 저장한다.

 

(s.length / 2)개 단위까지 확인한 후 compression의 길이를 출력하면 된다.