[Algorithm] 프로그래머스 - 압축

문제

[프로그래머스] 압축
(2018 KAKAO BLIND RECRUITMENT)

사용 알고리즘

- HASH MAP

해결방법

• 알파벳을 key로 index를 value로 가지는 alphaMap 생성
• Argument로 입력받은 msg를 이중 for문을 돌면서 탐색하는데, 이 때 alphaMap에 없던 코드면 추가해주고 answer 배열에 값을 인풋해준다.

테스트케이스1. Msg == KAKAO

• 바깥 for 문을 통해 msg의 첫번째 알파벳부터 LZW 압축 과정을 진행한다.
• 안쪽 for 문은 현재 시점의 알파벳을 시작으로 다음 알파벳을 하나씩 붙여가며 alphaMap에 해당 key값이 존재하는지 확인한다. 존재하는 가장 긴 key 값을 발견하게 되면, 그보다 더 긴 key값은 맵에 저장해주고, 해당 키에 대한 value값을 통해 압축한다.

K -> K키가 있는가?
Y-> K 다음으로 붙일 알파벳이 남았는가?

• Y-> KA 탐색

• N-> K 만 가지고 압축

N-> K 만 가지고 압축 & KA 키 저장
A -> A키가 있는가?
Y-> A 다음으로 붙일 알파벳이 남았는가?

• Y-> AK 탐색

• N-> A 만 가지고 압축

N-> A 만 가지고 압축 & AK 키 저장
K-> K키가 있는가? -> . . . -> KA 키가 있는가? -> . . . -> KA 가지고 압축 & KAO 키 저장
A
O -> O 키가 있는가? -> O 만 가지고 압축

 

소스코드

사용언어 : javascript

function solution(msg) {
    var ind, answer = [];
    let alphaMap = new Map();

    // 기본 알파벳맵 만들기
    for (var i = 65; i<91; i++){
        ind = i-64;
        alphaMap.set(String.fromCharCode(i), ind);
    }
    ind++;
    
    // 인덱스 추가 & LZW 압축 시작
    for (var x = 0; x<msg.length; x++) {
        var i, temp='';

        for (i = x; i < msg.length; i++){
            temp += msg[i];
            
            if (alphaMap.has(temp)) {
                if ((msg.length - (i + 1)) > 0) { // 체크할 알파벳이 더 있는 경우
                    continue;
                } else {
                    answer.push(alphaMap.get(temp)); 
                    x += temp.length -1
               }
            }  else { //인덱스가 존재하지 않는경우
                alphaMap.set(temp, ind); // 인덱스 추가
                ind++;

                var res = temp.slice(0, -1); // 마지막으로 추가한 단어 제거
                answer.push(alphaMap.get(res));
                x += res.length -1 // for문 간격 증가
                break;
            }
        }
    }
    return answer;
}

아스키 코드 변환

* let str = “ABC”
* str.charCodeAt(0) : 문자를 아스키 코드로 변환
* String.fromCharCode(65) : 아스키 코드를 문자로 변환

For .. in, For .. of

* let arr = [3, 5, 7]
* arr.foo = ‘hello’
* for (let i in arr) { console.log(i) } // “0”, “1”, “2”, “foo”
* for (let i of arr) { console.log(i) } // “3”, “5”, “7”

문자열 자르기 slice

> https://gent.tistory.com/414

[JavaScript] 문자열 자르기 (substr, substring, slice)

* slice(시작위치, 종료위치)
* str = ‘KAKAO’
* result = str.slice(0, -1) // “KAKA”
* result2 = str.slice(0, 2) // “”K”

0 1 2 3 4
K A K A O
-5 -4 -3 -2 -1

 

Array

> https://gent.tistory.com/295

[JavaScript] 자바스크립트 배열 추가, 삭제 방법 (push, pop, splice)

* arr = [‘a’, ‘b’, ‘c’]
* arr.push(‘d’)

한줄평

문법이 익숙하지 않다. . 문법을 더 익히도록 해야겠다.