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

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

프로그래머스

풀이

사전 정보를 저장할 Map<String, Integer> dict, 정답 숫자들을 저장할 리스트 List<Integer> answerWords를 생성한다.

int cnt는 사전의 색인 번호이며, dict에 단어가 추가될때마다 1씩 증가한다.

int cnt = 1; // 사전의 색인 번호
Map<String, Integer> dict // 사전
List<Integer> answerWords // 정답 숫자 리스트

 

길이가 1인 단어(알파벳)들로 dict 초기화한 후, 아래의 로직대로 dict와 answerWords를 구한다.

for (int i = 0; i < len; )
    // w 문자열 찾기 (= msg.substring(i, j) )
    for (int j = 0; j < len; j++)
   	  ..
    answerWords.add() // 정답리스트에 추가
    dict.put(새로운 문자열, cnt++) // 새로운 문자열 dict에 추가
    i = j;

 

마지막으로 answerWords에 담긴 숫자들을 int[] answer에 추가한다.

 

코드

import java.util.*;

class Solution {
    static int cnt = 1; // 사전의 색인 번호
    static Map<String, Integer> dict = new HashMap<>(); // 사전
    static List<Integer> answerWords = new ArrayList<>(); // 정답 숫자 리스트
    
    public int[] solution(String msg) {
        initDictionary();
        
        for (int i = 0; i < msg.length(); ) {
            // w(= msg.substring(i, j)) 문자열 찾기
            int j;
            for (j = i; j < msg.length(); j++) {
                String substr = msg.substring(i, j+1);
                if (!dict.containsKey(substr)) {
                    break;
                }
            }
            
            // answerWords에 색인 번호 추가
            String substr = msg.substring(i, j);
            int num = dict.get(substr);
            answerWords.add(num);
            
            // 새로운 문자열을 dict에 추가
            if (j < msg.length()) {
                dict.put(msg.substring(i, j+1), cnt++);
            }
            
            i = j;
        }
        
        // answerWords에 담긴 숫자들을 answer에 추가
        int[] answer = new int[answerWords.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = answerWords.get(i);
        }
        return answer;
    }
    
    static void initDictionary() {
        for (int i = 0; i < 26; i++) {
            char word = (char)('A' + i);
            dict.put(String.valueOf(word), cnt++);
        }
    }
}