[Javascript] [3차] 압축 (17684)

문제링크

코딩테스트 연습 - [3차] 압축

 

접근 방법

문자열 "MCK"가 주어졌을때,

사전(LZW)에 문자(M)가 있으면 다음문자(C)를 합친 문자를 만들어 LZW에 MC를 등록하고, 
LZW에서 문자 M의 index 번호를 answer에 넣는다.

만약 문자(M)과 다음문자(C)를 합친 문자 MC가 LZW에 있으면 다다음문자(K)를 넣어 MCK를 만들어 LZW에 등록
LZW에서 MC의 index 번호를 answer에 넣는다.
... 반복

(주의사항. 만약 LCM에 M도 있고 MC도 있어서 MCK를 만들었다면 문자열을 순회하는 index번호도 그만큼 건너 뛰어야한다. "M"(0) 다음 "C"(1)를 건너 뛰어 "K"(2)를 탐색해야함 )


우선 LZW 배열을 만든다. (0번째는 편의상 비운다. A === 1 이여야하기 때문에.)

1. 주어진 msg를 순환하면서 LZW에 해당 문자가 있는지 확인한다.

for(let idx = 0; idx < msg.length; idx++){
    let strLen = idx+1;
    let subStr = ""
    while(LZW.includes(msg.slice(idx,strLen)) && strLen <= msg.length){
        subStr = msg.slice(idx,strLen);
        strLen++;
    }
}​

(strLen <= msg.length는 종료 조건, 없으면 무환루프)
msg.slice(idx, idx+1)이 있으면, msg.slice(idx, idx+2) ... 를 반복하여 찾는다.

2. 찾은 문자열이 LZW에 있는지 확인하고 있다면 answer에 찾은 문자열의 index번호를 추가한다.

if(LZW.includes(subStr)) {
    answer.push(LZW.indexOf(subStr))
    if(!LZW.includes(msg.slice(idx, strLen))) LZW.push(msg.slice(idx,strLen))
    if(subStr.length > 1) idx += subStr.length - 1;
}

2.1 그리고 LZW에 찾은 문자열이 없다면 새로 추가한다.

if(!LZW.includes(msg.slice(idx, strLen))) LZW.push(msg.slice(idx,strLen))​

2.2 앞서 언급한 주의사항처럼 새로 만든 문자열의 길이 - 1만큼 msg를 순회하는 index 번호를 증가시킨다. 

if(subStr.length > 1) idx += subStr.length - 1;​

 

function solution(msg) {
    var answer = [];
    const LZW = ["", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]
    
    for(let idx = 0; idx < msg.length; idx++){
        let strLen = idx+1;
        let subStr = ""
        while(LZW.includes(msg.slice(idx,strLen)) && strLen <= msg.length){
            subStr = msg.slice(idx,strLen);
            strLen++;
        }

        
        if(LZW.includes(subStr)) {
            answer.push(LZW.indexOf(subStr))
            if(!LZW.includes(msg.slice(idx, strLen))) LZW.push(msg.slice(idx,strLen))
            if(subStr.length > 1) idx += subStr.length - 1;
        }

    }
    return answer;
}