Programmers - 압축

문제

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

프로그래머스

 

 

문제 접근

• LZW 압축의 동작을 그대로 구현하는 것이다. 이때 단어가 세팅된 사전에 존재하는지를 체크하고 없다면 그 단어를 사전에 넣고, 존재한다면 해당 색인(index)를 넣음으로서 압축을 할 수 있다.
• 나이브하게 접근하면 사전을 순회하면서 현재 단어가 사전에 존재하는지 비교를 하며 존재한다면 인덱스를 반환하고 존재하지 않는다면 사전에 포함시키는 동작을 구현하면 된다.
  • 하지만 이는 단어가 존재하는지 확인하기 위해 배열을 계속해서 순회해야 함으로 시간복잡도 면에서 효율적이지 못하다.
• 사용한 것은 HashMap으로 색인번호와 알파벳을 매칭시켜 HashMap으로 관리하고, containsKey를 통해 확인함으로서 존재 유무를 O(1)에 알아낼 수 있다.
• 이후에는 2중 반복문을 통해 색인 번호를 계속해서 갱신하는 방식으로 해결하였다. 전체적인 시간 복잡도는 O(N^2)가 되며 입력 문자열 msg의 길이가 최대 1000 이기 때문에 100만으로 일반적인 시간 제한 1초를 매우 널럴하게 통과할 수 있다.

 

 

답안 코드

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        ArrayList<Integer> ans = new ArrayList<>();
        HashMap<String, Integer> dict = new HashMap<>();
        boolean[] visited = new boolean[msg.length()];
        
        for(int i = 0; i < 26; i++){
            char character = (char)('A' + (char)i);
            dict.put(Character.toString(character), i + 1);
        }
        
        int idx = 27;
        
        for(int i = 0; i < msg.length(); i++){
            // 해당 문자가 이미 압축된 단어에 포함된 문자일 경우 건너뛴다.
            if(visited[i]){
                continue;
            }
            
            StringBuilder sb = new StringBuilder();
            sb.append(msg.charAt(i));
            
            int searchIdx = 0;
            
            // 사전에 해당 단어가 존재한다면
            if(dict.containsKey(sb.toString())){
                visited[i] = true; // 압축된 단어에 포함되었다고 체크하고
                searchIdx = dict.get(sb.toString()); // 단어에 해당하는 색인 번호를 넣는다.
            }
            
            // 이후 현재 입력과 일치하는 가장 긴 문자열 w를찾는다.
            for(int j = i + 1; j < msg.length(); j++){
                sb.append(msg.charAt(j));
                
                if(dict.containsKey(sb.toString())){
                    visited[j] = true;
                    searchIdx = dict.get(sb.toString());
                } else{
                    // 사전에 존재하지 않는 단어라면 사전에 추가하고 더 이상 돌 필요가 없으므로 탈출한다.
                    dict.put(sb.toString(), idx++);
                    break;
                }
            }
            
            // 최종적으로 찾은 단어의 색인을 답에 넣는다.
            ans.add(searchIdx);
        }
        
        int[] answer = new int[ans.size()];
        
        for(int i = 0; i < ans.size(); i++){
            answer[i] = ans.get(i);
        }
        
        return answer;
    }
}