[프로그래머스] 17684. 압축

문제 링크

[프로그래머스] 17684. 압축

풀이 과정

문제 설명

map 자료구조를 이용해 사전을 구현합니다. 먼저 A 부터 Z 까지 문자열을 사전에 등록해줍니다.

int count = 1;
for (int i = 65; i <= 90; i++) {
    hashMap.put(Character.toString((char) i), count++);
}

시작 인덱스 start 는 문자열 msg 를 순회하며 증가합니다. end 는 start 를 시작으로, map 에 포함되어 있는 가장 긴 문자열을 찾아 그 끝 인덱스 위치를 갖습니다.

while (end + 1 <= msg.length() && hashMap.containsKey(msg.substring(start, end + 1))) {
    end++;
}

가장 긴 문자열을 찾았으면, 해당 단어의 색인을 반환할 리스트에 추가해줍니다.

answer.add(hashMap.get(msg.substring(start, end)));

다음 글자가 있다면, 새로 만들어진 w+c 문자열을 다음 번 색인으로 사전에 추가해줍니다.

if (end < msg.length()) {
    hashMap.put(msg.substring(start, end + 1), count++);
}

위 과정을 msg 문자열이 끝나는 지점까지 반복합니다.

코드

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static ArrayList<Integer> solution(String msg) {
        ArrayList<Integer> answer = new ArrayList<>();
        Map<String, Integer> hashMap = new HashMap<>();

        int count = 1;
        for (int i = 65; i <= 90; i++) {
            hashMap.put(Character.toString((char) i), count++);
        }

        int start = 0;
        while (start < msg.length()) {
            int end = start;

            while (end + 1 <= msg.length() && hashMap.containsKey(msg.substring(start, end + 1))) {
                end++;
            }

            answer.add(hashMap.get(msg.substring(start, end)));
            if (end < msg.length()) {
                hashMap.put(msg.substring(start, end + 1), count++);
            }

            start = end;
        }

        return answer;
    }

    public static void main(String[] args) {
        solution("KAKAO");
//        solution("TOBEORNOTTOBEORTOBEORNOT");
//        solution("ABABABABABABABAB");
    }
}

Javascript

const solution = (msg) => {
    var answer = [];
    let map = new Map();
    
    let count = 1;
    for(let idx = 65; idx <= 90; idx++) {
        map.set(String.fromCharCode(idx), count++);
    }

    let start = 0;    
    while(start < msg.length) {
        let end = start;
        
        while(end + 1 <= msg.length && map.has(msg.substring(start, end + 1))) {
            end++;
        }

        answer.push(map.get(msg.substring(start, end)));

        if(end < msg.length) {
            map.set(msg.substring(start, end+1), count++);
        }

        start = end;
    }

    return answer;
};

solution("KAKAO");
// solution("TOBEORNOTTOBEORTOBEORNOT");
// solution("ABABABABABABABAB");