Java - [프로그래머스 Lv.2]17684 - [3차]압축

출처

https://school.programmers.co.kr/learn/courses/30/lessons/17684

문제

메시지 압축하는 LZW 알고리즘을 만드는 문제입니다.다음과 같은 과정에 따라 압축을 진행합니다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

단계별로 살펴보도록 하겠습니다.

리스트 초기화

길이가 1인 모든 단어(대문자)를 List에 미리 저장해둡니다.

char alpha = 'A';
        for (int i = 0; i < 26; i++) {
            dict.add(alpha + "");
            alpha++;
        }

String 리스트인 dict에 대문자 A부터 Z까지 값을 넣어주어 초기화 해줍니다.

전체 for문 구성

사전에서 현재 입력과 일치하는 가장 긴 문자열 W를 찾고, 반복하여 탐색하기 위해 큰 for문을 사용합니다.

 	for (int i = 0; i < msg.length(); i++) {
            String w = msg.charAt(i) + "";
            // w가 마지막 문자일 경우 종료
            if (i == msg.length() -1) {
                answer.add(dict.indexOf(w) + 1);
                break;
            }
            
            String c = msg.charAt(i+1) + "";
			
            // w+c가 존재하는 경우, w는 w+c로 업데이트하고 i의 값을 하나 올려줌
            while (dict.contains(w+c)) {
                w = w + c;
                i++;

				//i가 문자열의 마지막인 경우, c를 공백으로 만들고 while문 탈출
                if (i == msg.length() -1) {
                    c = "";
                    break;
                }

				// c 또한 w 다음 문자로 업데이트
                c = msg.charAt(i+1) + "";
            }
			// dict에 등록되어 있지 않다면 추가
            if (!dict.contains(w+c)) {
                dict.add(w+c);
            }

            int x = dict.indexOf(w);
            if (x != -1) {
            	// 색인 번호를 answer에 출력
                answer.add(x + 1);
            }

			// C에 들어온 문자가 마지막 문자인 경우
            if (i == msg.length() && !c.equals("")) {
                answer.add(dict.indexOf(c) + 1);
            }


        }

자세한 설명은 코드에 주석으로 달아 두었습니다. 문제 해결 과정대로 구성을 하였으니, 그것을 생각하고 코드와 주석을 함께 보신다면 금방 이해가 되실거라고 생각합니다.

전체 코드

import java.util.*;
import java.math.*;

class Solution {

    List<Integer> answer = new ArrayList<>();
    List<String> dict = new ArrayList<>();

    public int[] solution(String msg) {

        char alpha = 'A';
        for (int i = 0; i < 26; i++) {
            dict.add(alpha + "");
            alpha++;
        }

        for (int i = 0; i < msg.length(); i++) {
            String w = msg.charAt(i) + "";
            // w가 마지막 문자일 경우 종료
            if (i == msg.length() -1) {
                answer.add(dict.indexOf(w) + 1);
                break;
            }
            
            String c = msg.charAt(i+1) + "";

            // w+c가 존재하는 경우, w는 w+c로 업데이트하고 i의 값을 하나 올려줌
            while (dict.contains(w+c)) {
                w = w + c;
                i++;

                //i가 문자열의 마지막인 경우, c를 공백으로 만들고 while문 탈출
                if (i == msg.length() -1) {
                    c = "";
                    break;
                }

                // c 또한 w 다음 문자로 업데이트
                c = msg.charAt(i+1) + "";
            }

            // dict에 등록되어 있지 않다면 추가
            if (!dict.contains(w+c)) {
                dict.add(w+c);
            }

            int x = dict.indexOf(w);
            if (x != -1) {
                // 색인 번호를 answer에 출력
                answer.add(x + 1);
            }

            // C에 들어온 문자가 마지막 문자인 경우
            if (i == msg.length() && !c.equals("")) {
                answer.add(dict.indexOf(c));
            }


        }

        
        return answer.stream().mapToInt(i -> i).toArray();
    }


}