자바스크립트 예제: 압축 (카카오 2018 코딩테스트 기출)

프로그래머스 사이트에서 문제 풀기

코드

function solution(msg) {
    var answer = [];
    
    // 사전 작성
    const dict = {}
    for(let i = 1; i <= 26; i++) {
        dict[String.fromCharCode(i + 64)] = i
    }
    let maxIdx = 26
    
    let idx = 0
    let msgLen = msg.length
    while(idx < msgLen) {
        let currentMaxStr = ""
        for(let j = idx; j < msgLen; j++) {
            const target = msg.substring(idx, j + 1)
            if(dict[target]) {
                currentMaxStr = target
            } else {
                dict[target] = ++maxIdx
                break
            }
        }
        answer.push(dict[currentMaxStr])
        // idx를 currentMaxStr 만큼 증가
        idx += currentMaxStr.length
    }
    
    return answer;
}

일단 정답 처리된 코드입니다. 밑에부터는 각 부분별 분석입니다.

해설

먼저 사전을 객체 형식으로 작성합니다. 문제에서는 "A" 부터 "Z"까지 사전이 미리 주어져 있다고 했으므로 그에 대한 사전을 작성합니다. key가 문자, value가 인덱스 번호이면 문제 풀기에 유리합니다. String.fromCharCode(숫자)는 해당 숫자의 아스키 코드 및 유니코드를 반환합니다. 예를 들어 String.fromCharCode(65)는 문자 "A"를 반환합니다.

maxIdx 변수는 현재 사전에서 최대 인덱스를 저장합니다. 객체 내에서 현재 최대 인덱스를 알아낼 수 있는 방법도 있겠지만 그냥 별도의 변수에서 따로 관리하는게 편할 것 같아서 분리했습니다.

// 사전 작성
const dict = {}
for(let i = 1; i <= 26; i++) {
    dict[String.fromCharCode(i + 64)] = i
}
let maxIdx = 26

다음 msg 문자 길이만큼 반복문을 돌면서 그 문자부터 시작해서 문자 끝까지 2중 반복문을 사용해 추출해 보겠습니다. 위의 정답코드와는 다른데 일단 for문을 사용해 보겠습니다.

for(let i = 0; i < msg.length; i++) {
    for(let j = i; j < msg.length; j++) {
        console.log(msg.substring(i, j + 1))
    }
}

위와 같은 문자열들이 추출됩니다.

다음으로 저 2중 반복문을 순회하면서 사전에 문자열이 있다면 정답 배열에 집어넣고, 사전에 없는 문자열이라면 새로 추가하는 코드를 작성해 보겠습니다.

먼저 사전에 있다면 바로 정답에 집어넣지 않고 사전에 있는 더 긴 문자열이 있는지 확인하기 위해 currentMaxStr 이라는 변수를 만들겠습니다. 위 문제 예시 중 "KAKAO" 의 경우 3회전 부분에서 "K"도 사전에 있고, "KA"도 사전에 있는 경우 "K"는 중복 출력하지 않고 "KA" 만 출력해야 하기 때문입니다.

그리고 이 2중 반복문은 뒤로 갈수록 더 긴 문자열을 target으로 하므로 길이를 판별하는 별도의 조건은 없어도 됩니다.

for (let i = 0; i < msg.length; i++) {
    let currentMaxStr = ""
    for (let j = i; j < msg.length; j++) {
        const target = msg.substring(i, j + 1)
        if(dict[target]) { // 사전에 있는 문자열이라면
            currentMaxStr = target // 일단 바로 정답에 넣지 않고 더 긴 문자열이 있는지 보류
        } else {
            // 사전에 없는 값이면
            dict[target] = ++maxIdx // maxIdx를 1 증가 시킨 값을 인덱스로 하여 새로 사전에 추가
            break // 사전 추가 이후 더 진행되면 안되므로 현재 for문 중단
        }
        answer.push(dict[currentMaxStr])
    }
}

이렇게 하면 뭔가 나오긴 하는데 문제에서 요구하는 것과 약간 다릅니다.

중간에 1이 중복되어 나오는 것을 볼 수 있습니다. 제가 계속 해맸던 부분인데 2중 반복문에서 첫 반복문을 for문으로 쓰면 안됩니다.

위 그림에서 주황색 부분은 원래 출력이 되면 안되는데, 왜 되는 것일까요?

첫 번째 for문은 i가 1씩 증가하면서 모든 텍스트를 검사하고, 사전에 있으면 무조건 출력을 하도록 되어있는데 여기서 중복된 출력을 검사할 부분이 없어서 문제가 생기는 것입니다. 예를 들어 "KA"가 사전에 있으면 다음 "A"는 애초에 "KA"에 포함된 부분이므로 검사할 필요 없이 패스해야 됩니다.

이것을 해결하는 방법은 여러 가지가 있겠지만, 저는 첫 번째 반복문을 for에서 while문으로 변경한 뒤, 현재 사전에 있는 최대 글자만큼 인덱스를 증가시키는 방법을 사용했더니 정상적으로 작동을 했습니다.

let idx = 0
const msgLen = msg.length
while (idx < msgLen) {
    let currentMaxStr = ""
    for (let j = idx; j < msgLen; j++) {
        const target = msg.substring(idx, j + 1)
        if (dict[target]) { // 사전에 있는 문자열이라면
            currentMaxStr = target // 일단 바로 정답에 넣지 않고 더 긴 문자열이 있는지 보류
        } else {
            // 사전에 없는 값이면
            dict[target] = ++maxIdx // maxIdx를 1 증가 시킨 값을 인덱스로 하여 새로 사전에 추가
            break // 사전 추가 이후 더 진행되면 안되므로 현재 for문 중단
        }
    }
    answer.push(dict[currentMaxStr])
    idx += currentMaxStr.length // idx를 현재 사전에 있는 최대 길이만큼 증가
}