[Java] 프로그래머스(level-2) - 압축

문제 풀이

---

이 문제는 문제에서 주어지는 LZW 압축 구현 방법을 그대로 구현하면 된다.

아이디어 도출

먼저 A에서부터 Z까지의 문자는 사전이 초기화될 때 이미 존재하도록 설정해두기 때문에 A~Z에서와 다음 문자를 결합한 문자열의 사전 존재여부를 확인해야 한다.

이 과정을 간단하게 살펴보면 다음과 같다.

1. 현재 문자나 문자열이 사전에 존재하는지 확인하고 사전에 있다면 [현재 문자(문자열) + 다음 문자] 값을 사전에서 찾는다.
2. [현재 문자(문자열) + 다음 문자] 값이 사전에 없다면 사전 마지막 번호로 등록한다.
3. 이후, [현재 문자(문자열) + 다음 문자] 값의 사전 번호(인덱스 값)룰 출력한다.
4. [현재 문자(문자열) + 다음 문자] 값의 다음 문자부터 해당 과정을 반복한다.

말로 설명하면 어려우니 KAKAO를 예시로 들어보자.

예시 -> [KAKAO]

K는 사전에 있으니
현재 문자(K) + 다음 문자(A) = KA 검사
문자열 KA는 사전에 없으니 사전에 인덱스 27로 넣기
현재 문자 K의 인덱스 11 출력
다음 문자(A)로 넘어가기

->

현재 문자인 A는 사전에 있으니
현재 문자(A) + 다음 문자(K) = AK 검사
문자열 AK는 사전에 없으니 인덱스 28로 넣기
현재 문자 A의 인덱스 1 출력
다음 문자(K)로 넘어가기

->

현재 문자인 K는 사전에 있으니
현재 문자(K) + 다음 문자(A) = KA 검사
문자열 KA는 사전에 있으니
문자열 (KA) + 다음 문자(O) = KAO 검사
문자열 KAO는 사전에 없으니 인덱스 29로 넣기
현재 문자열 KA의 인덱스 27 출력
문자열의 다음 문자(O)로 넘어가기

->

O는 마지막 문자이니 O의 인덱스 15 출력

정답 = [11, 1, 27, 15]

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

    public int[] solution(String msg) {

        LinkedHashMap<String, Integer> hm = new LinkedHashMap<>();
        ArrayList<Integer> result = new ArrayList<>();

        for(int i=65; i<=90; i++) {
            String alph = Character.toString(i);
            hm.put(alph, i-64);
        }

        for(int i=0; i<msg.length(); i++) {
            // 현재 문자를 선언
            String w = String.valueOf(msg.charAt(i));
            
            // 현재 문자가 마지막 문자라면 for문 순회를 멈춘다.
            // 이때, 마지막 문자의 map에서의 값을 result에 삽입하고 루프를 종료한다. 
            if(i == msg.length()-1) {
                result.add(hm.get(w));
                break;
            }

            // 현재 문자를 기준으로 다음 문자를 선언
            String c = String.valueOf(msg.charAt(i+1));

            
            // 현재 문자나 문자열이 사전에 존재한다면 while문을 순회하면서 w와 c를 갱신한다.
            // w는 w+c로, c는 갱신된 w(w+c)의 다음 글자로 갱신한다.
            while(hm.containsKey(w + c)) {
                w = w + c;
                i++;
                // 현재 인덱스가 마지막 문자라면 다음 글자를 갱신할 필요가 없음!
                if(i == msg.length()-1) {
                    c = "";
                    break;
                }
                c = String.valueOf(msg.charAt(i+1));
            }

            // 사전에 없는 문자라면 등록한다.
            if(!hm.containsKey(w+c)) {
                hm.put(w+c, hm.size()+1);
            }
            result.add(hm.get(w));
            
        }
   
        // stream을 이용해 List를 Array로 변환
        int[] answer = result.stream()
            .mapToInt(Integer::intValue)
            .toArray();

        return answer;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        String msg = "KAKAO";
        // String msg = "TOBEORNOTTOBEORTOBEORNOT";
        // String msg = "ABABABABABABABAB";

        sol.solution(msg);
    }

}

회고

• ---

출처

- —

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.