프로그래머스 Lv.2) 압축

2018 KAKAO BLIND RECRUITMENT [3차]

압축

코딩테스트 연습 - [3차] 압축

풀이

오늘 푼 문제중에 제일 쉽게 푼 문제였다. 기본 알파벳 A-Z 까지 사전에 미리 등록하고, 입력받은 문자열을 돌면서 조건에 따라 사전에 추가, 출력할 색인 번호를 담아주었다.

사전으로는 HashMap을 선택하여 특정 문자를 포함하고 있는지, 포함하고 있다면 색인 번호를 받아왔다.

출력할 색인 번호는 로직에 따라 ArrayList에 순서대로 담은 뒤, 마지막에 해당 크기만큼 배열을 만들어 저장해주어 리턴했다.

 

로직

1. 알파벳(A-Z) 까지 미리 사전에 담아둔다. (inItDictionary 메소드)

2. 문제에서 제시한 LZW(Lempel–Ziv–Welch) 메소드를 만들어 주었다.

 2-1. 문자열을 돌면서 가장 길게 이어지는 문자열이 사전에 있는지 체크한다.

 2-2. 사전에 있다면 문자를 하나씩 더해가면서 계속 검증한다.

 2-3. 사전에 없는 문자라면 사전에 등록해주고, 마지막에 붙인 문자를 빼서, 사전에서 가장 긴 문자열인 문자의 색인번호를 받아와 ArrayList에 추가한다.

 2-4. 전체 문자열에서 색인 번호를 추가한 문자 이후로 잘라주고, LZW의 파라미터로 넘겨 다시 검증한다.

       ( ex : 전체 문자열 길이가 16, 가장 긴 문자가 0~3이었다면, 4~15까지 잘라서 다시 LZW를 진행)

3. LZW에서, 특정 Index부터 전체 문자열의 마지막 인덱스까지 이어지는 글자가 존재하는 경우를 if문으로 설정해서 색인 번호를 추가한다.

4. 색인 번호가 저장된 ArrayList의 크기만큼 배열을 만들어 저장한 뒤, 리턴해준다.

 

코드

import java.util.HashMap;
import java.util.ArrayList;

class Solution {
    HashMap<String,Integer> dictionary;
    int idx;
    ArrayList<Integer> idxList;
    public int[] solution(String msg) {
        inItDic();
        makeLZW(msg);
        return getAnswer();
    }
    
    private void inItDic() {
        dictionary = new HashMap<>();
        for(int i=1; i<=26; i++) {
            char ch = (char)(i+64);
            dictionary.put(Character.toString(ch),i);
        }
        idx =27;
        idxList = new ArrayList<>();
    }
    
    private void makeLZW(String msg) {
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<msg.length(); i++) {
            sb.append(msg.charAt(i));
            if(!dictionary.containsKey(sb.toString())) {
                dictionary.put(sb.toString(),idx++);
                sb.deleteCharAt(sb.length()-1);
                idxList.add(dictionary.get(sb.toString()));
                makeLZW(msg.substring(sb.length()));
                return;
            } else if(i == msg.length()-1) {
                idxList.add(dictionary.get(sb.toString()));
            }
        }
    }
    
    private int[] getAnswer() {
        int[] answer = new int[idxList.size()];
        for(int i=0; i<answer.length; i++) {
            answer[i] = idxList.get(i);
        }
        return answer;
    }
}