[프로그래머스 - Java] [3차] 압축 (2018 KAKAO BLIND RECRUITMENT)

문제

programmers.co.kr/learn/courses/30/lessons/17684

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

설명

LZW 압축은 다음 과정을 거친다.

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

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.

      ArrayList<Integer> list = new ArrayList<>(); //출력할 색인 번호를 담을 ArrayList
      HashMap<String, Integer> map = new HashMap<>(); // 사전의 값을 담을 HashMap
        
      for(int i = 1; i < 27; i++) { //(A~Z, 1~26) LZW 1번 과정
          char alpha = (char) (64+i);
          map.put(String.valueOf(alpha), i);
      }    

 

2, 3, 4의 과정

for(int i = 0; i < msg.length(); i++) { //단어의 처음부터 끝까지 하나하나 확인한다.
	String key = msg.charAt(i) + ""; //i번째에 해당하는 단어 즉 현재 입력(w)
	int index = i + 1; //다음 글자(c)를 얻기 위한 index

	while(index <= msg.length()) { //단어의 마지막까지 확인하면서 사전에 있나 없나 확인해야 함
		if(index == msg.length()) { //단어의 마지막까지온 경우
			list.add(map.get(msg.substring(i))); //i부터 마지막 단어까지 글자에 대응되는 색인 번호를 출력
			i = index; //i값을 index값으로 설정해 반복문이 끝나도록 한다. (* 설명 참고)
			break;
		}


		String nextKey = msg.substring(i, index+1); //현재 입력(w) + 다음 글자(c)
		if(map.containsKey(nextKey)) { //w+c가 있다면 다시 index를 하나 높여 다음 글자가 사전에 있는지 확인
			index++;
		} else { //다음 글자가 사전에 없음
            //반복문을 돌며 다음 문자가 있을 때마다 key의 길이는 변하기 때문에 구해진 다음 글자의 index전까지로 key를 다시 설정한다.
			key = msg.substring(i, index); 
			list.add(map.get(key)); //그 때의 key값에 대응되는 색인번호 출력
			map.put(nextKey, map.size()+1); //w+c 사전에 추가
			i = index-1; //다음 글자의 index부터 다시 LZW
			break;
		}
	}
}

 

ex) KAKAO

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O		15

 

표를 위의 그림처럼 이해하면 된다.

내 코드의 key 변수가 현재 입력 w를 의미하고, nextKey 변수가 사전에 추가될 w+c를 의미한다.

현재 A~Z까지 1~26의 색인 번호를 가지고 사전에 등록되어있다.

 

 

 

먼저 가장 첫 번째 K를 검사한다. K는 사전의 11번에 등록되어있다.

그럼 다음을 검사한다.

다음 단어인 KA는 사전에 없기 때문에 그전의 key인 K의 색인 번호 11을 출력하고 KA가 사전의 27번에 등록된다.

 

두 번째 단어인 A 역시 AK는 사전에 없기 때문에 A의 색인 번호 1을 출력하고 AK가 사전의 28번에 등록된다.

 

세 번째 단어인 K는 사전에 있다. 그다음 단어인 KA 역시 사전에 있다.

그럼 그 다음 단어인 KA + O까지 검사해야 한다.

O는 단어의 마지막이기 때문에 그 이상은 검사하지 않는다.

결론적으로 KA의 색인 번호인 27을 출력하고 KAO가 사전의 29번에 등록된다.

 

그리고 마지막 O가 15를 출력하고 로직이 끝나게 된다.

 

* 설명 참고

두 번째 예시인 TOBEORNOTTOBEORTOBEORNOT의 경우

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
RN	O	32	41: RNO
OT		34

마지막에서 두번째 단어인 O부터 마지막 단어 T까지가 남았을 때

O의 다음 글자는 OT이고 사전에 등록되어있다.

그럼 OT의 색인 번호 34를 출력하고 모든 LZW 루프가 끝나야 한다.

그래서 i = index; 구문을 추가해 반복을 끝내야 한다.

만약 이 구문이 없다면 다시 T에 해당하는 i 값을 시작으로 LZW를 수행하기 때문이다.

전체 코드

import java.util.*;

class Solution {
	public int[] solution(String msg) {
		ArrayList<Integer> list = new ArrayList<>();
		HashMap<String, Integer> map = new HashMap<>();

		for(int i = 1; i < 27; i++) {
			char alpha = (char) (64+i);
			map.put(String.valueOf(alpha), i);
		}    

		for(int i = 0; i < msg.length(); i++) {
			String key = msg.charAt(i) + "";
			int index = i + 1;

			while(index <= msg.length()) {
				if(index == msg.length()) {
					list.add(map.get(msg.substring(i)));
					i = index;
					break;
				}

				String nextKey = msg.substring(i, index+1);

				if(map.containsKey(nextKey)) { 
					index++;
				} else { 
					key = msg.substring(i, index);
					list.add(map.get(key)); 
					map.put(nextKey, map.size()+1); 
					i = index-1;
					break;
				}
			}
		}

		int[] answer = new int[list.size()];
		for(int i = 0; i < list.size(); i++) {
			answer[i] = list.get(i);
		}

		return answer;
	}
}

 

재귀 함수를 쓰는 또 다른 코드

import java.util.*;

class Solution {
    public static HashMap<String, Integer> map;
	public static ArrayList<Integer> list;
	public static int idx;
    
	public int[] solution(String msg) {
				list = new ArrayList<>();
		map = new HashMap<>();
		idx = 27;

		for(int i = 1; i < 27; i++) {
			char alpha = (char) (64+i);
			map.put(String.valueOf(alpha), i);
		}    

		makeLZW(msg);

		int[] answer = new int[list.size()];
		for(int i = 0; i < list.size(); i++) {
			answer[i] = list.get(i);
		}

		return answer;
	}
    
    public static void makeLZW(String msg) {
		StringBuffer sb = new StringBuffer();
		for(int i=0; i < msg.length(); i++) {
			sb.append(msg.charAt(i));
			if(!map.containsKey(sb.toString())) {
				map.put(sb.toString(), idx++);
				sb.deleteCharAt(sb.length()-1);
				list.add(map.get(sb.toString()));
				makeLZW(msg.substring(sb.length()));
				return;
			} else if(i == msg.length()-1) {
				list.add(map.get(sb.toString()));
			}
		}
	}
}

GITHUB

github.com/KwonMinha/Programmers/blob/master/2018_Kakao_Blind_Recruitment/src/LZW.java

KwonMinha/Programmers