[프로그래머스 코딩테스트] 2020 KAKAO BLIND RECRUITMENT - 문자열 압축

 Java Script 

[프로그래머스 코딩테스트] 2020 KAKAO BLIND RECRUITMENT - 문자열 압축

👉 하루에 한번씩 코딩 실력을 기르기 위해 시작하는 프로그래머스 코딩테스트

👉 코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 문자열 압축

 

문제 설명 및 제한사항

👉 문제

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "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는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

 

정답 및 풀이

👉 정답

function solution(s) {
    var answer = 0;
    let zip_s_map = new Map();
    if(s.length >= 1 && s.length <= 1000) {
        for(let i in s) { //문자열 길이만큼 반복
            // step1] 문자열 인덱스 1부터 시작으로 바꿔주기
            i = parseInt(i)+1; // 0시작 인덱스를 1로.
            // step2] match,정규식 사용하여 문자열을 i로 나누어 배열처리
            let splits_s_array = s.match(new RegExp('.{1,'+i+'}', 'g'));
            // step3] splits된 s 배열을 압축한 문자열 만들기
            
            let last_s = ''; //split_s를 forEach할 때 마지막 글자 대입용도
            let dump_s = ''; //splits_s를 forEach하면서 만들어 줄 압축문자열
            let dump_i = 1; //압축문자열에서 사용할 중복문자의 개수
            splits_s_array.forEach(split_s => {
                
                if(!dump_s) { dump_s += split_s; }
                else {
                    if(last_s == split_s) { //마지막 문자와 현재 문자가 같다면
                        // dump_s에 마지막 글자에 숫자형식이 있다면 그 숫자를 빼고 최신 숫자 반영
                        dump_s = dump_s.replace(/[0-9]+$/,'');
                        dump_i++; //같은글자 개수 늘리기
                        dump_s += dump_i;
                    }else{
                        dump_i = 1; //dump_i 값 초기화
                        dump_s += split_s;
                    }
                }
                last_s = split_s; //마지막 문자 넣어주기
            });
            zip_s_map.set(i,dump_s);
        }
        let best_short_num = 1000; // s는 1000이하이니 1000으로 초기화해줌.
        zip_s_map.forEach(zip_s => {
            if(zip_s.length < best_short_num) best_short_num = zip_s.length;
        });
        answer = best_short_num;
    }
    return answer;
}

 

👉 풀이

1. 문자열 개수만큼 잘라서 담아둘 zip_s_map을 선언합니다.
2. s는 1부터 1000까지 길이의 문자열 처리를 해줍니다.
3. 문자열 s의 길이만큼(1부터 문자열 길이까지 잘라서 압축하는 경우의수)  for문을 반복합니다
4. for문으로인한 0으로시작되는 인덱스값을 1부터 시작으로 바꿔줍니다.
5. 정규식을 사용하여 문자열을 반복되는 i값(1부터 문자열길이까지 잘라주는 경우의 수 만큼)으로 잘라 배열로 만듭니다.
6. 만들어진 splits_s_array 배열을 각 단위별로 비교하기위해 forEach처리합니다
7. dump_s 변수를 만들어 잘라진 배열 단위를 비교 하며 last_s값을 대입, 같은값이 있다면 숫자를 대입, 없다면 문자를 대입합니다
8. 같은값이 2 이상이 될 경우 마지막 값을 정규식으로 없애주고 새로운 숫자 (2이상의 값)을 부여합니다.
9. 문제에서는 압축 할 때, 숫자가 앞으로 문자가 뒤로 가지만 return값은 압축된 문자열이 아닌 문자열의 개수이기 때문에 후처리 x
10. 1번에서 선언한 zip_s_map에 경우의 수만큼 압축한 문자들을 넣어줍니다.
11. zip_s_map을 forEach처리하여 map에 저장된 문자열중 길이가 가장 작은 길이를 best_short_num 변수에 넣어줍니다.
12. answer 값에 가장 작은 길이의 압축문자열.length값을 넣어주고 return해주면 끝

 

 

마무리

👉 string.match(new RegExp('.{1,'+나누고싶은숫자+'}', 'g')); // 문자열을 나누고싶은 숫자만큼 잘라 배열로 만들어줍니다

 

👉 stirng.replace(/[0-9]+$/,'');  // string문자열중 마지막($)이 숫자형태면 빈값으로 바꾸어줍니다.