[3차] 압축 with Java

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

프로그래머스

 

1️⃣ 어떻게 문제를 풀까?

먼저 해당 단어가 사전에 있는 단어로 시작하는지 확인해야 됨! 따라서 String로 검색해야 하므로 Map 자료구조를 사용! 

그런데 압축 할 때마다 단순히 Map의 모든 Key 값으로 검색하면 느려질 것 같음.. (압축을 한번 할 때 마다 사전에 한 단어는 넣기 때문!)

그래서 Map의 Key를 해당 단어의 첫 글자(ex. 'A')로 하고 value를 해당 글자로 시작하는 단어 리스트로 정의!

그런데 사전에 있는 단어는 길이가 다름! 같은 'A'로 시작하는 단어더라도 더 긴 단어와 매치되면 해당 단어로 압축해야됨! (예를 들어 'APP'라는 단어가 있고, 사전에 'A', 'AP'가 있다면 'AP'와 매치 시켜줘야함!) → 정렬 필요!

 

import java.util.*;

class Solution {
    public class Word {
        String word;
        int index;
        
        public Word(String word, int index) {
            this.word = word;
            this.index = index;
        }
    }
    
    public int[] solution(String msg) {
        List<Integer> compression = new ArrayList<>();
        Map<Character, List<Word>> dictionary = new HashMap<>();
        for(char ch = 'A'; ch < 'A' + 26; ++ch) {
            List<Word> list = new ArrayList<>();
            list.add(new Word(String.valueOf(ch), ch - 'A' + 1));
            dictionary.put(ch, list);
        }
        
        int counter = 26;
        boolean isFinish = false;
        while(msg.length() > 0 && !isFinish) {
            char key = msg.charAt(0);
            List<Word> list = dictionary.get(key);
            list.sort((a, b) -> b.word.length() - a.word.length());
            for(Word word : list) {
                if(msg.startsWith(word.word)) {
                    compression.add(word.index);
                    if(msg.length() == word.word.length()) {
                        isFinish = true;
                        break;
                    }
                    list.add(new Word(word.word + String.valueOf(msg.charAt(word.word.length())), ++counter));
                    msg = msg.substring(word.word.length());
                    break;
                }
            }
        }
        
        return compression.stream()
            .mapToInt(i -> i)
            .toArray();
    }
}

 

💡 매 압축 마다 정렬하는 것이 별로니, PriorityQueue를 사용해보자!

import java.util.*;

class Solution {
    public class Word {
        String word;
        int index;
        
        public Word(String word, int index) {
            this.word = word;
            this.index = index;
        }
    }
    
    public int[] solution(String msg) {
        List<Integer> compression = new ArrayList<>();
        Map<Character, PriorityQueue<Word>> dictionary = new HashMap<>();
        for(char ch = 'A'; ch < 'A' + 26; ++ch) {
            PriorityQueue<Word> pq = new PriorityQueue<>((a, b) -> b.word.length() - a.word.length());
            pq.add(new Word(String.valueOf(ch), ch - 'A' + 1));
            dictionary.put(ch, pq);
        }
        
        int counter = 26;
        boolean isFinish = false;
        while(msg.length() > 0 && !isFinish) {
            char key = msg.charAt(0);
            PriorityQueue<Word> pq = dictionary.get(key);
            PriorityQueue<Word> copy = new PriorityQueue<>(pq);
            while(!pq.isEmpty()) {
                Word word = pq.poll();
                if(msg.startsWith(word.word)) {
                    compression.add(word.index);
                    if(msg.length() == word.word.length()) {
                        isFinish = true;
                        break;
                    }
                    copy.add(new Word(word.word + String.valueOf(msg.charAt(word.word.length())), ++counter));
                    dictionary.put(key, copy);
                    msg = msg.substring(word.word.length());
                    break;
                }
            }
        }
        
        return compression.stream()
            .mapToInt(i -> i)
            .toArray();
    }
}

 

그렇게 더 빠르진 않다..ㅎ