[프로그래머스/자바] 압축 풀이 - 2018 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2018 KAKAO BLIND RECRUITMENT 3차 Level 2 문제다.

 

 

 

문제에 나와있는 LZW 압축 과정 순서대로 구현하면 된다.

단계 5는 단계 2로 돌아가는 것이므로 재귀적으로 함수를 구현했다.

과정을 읽기보다는 입출력 예시를 참고하는 게 더 이해가 쉬웠다.

 

 

 

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

		char c = 'A';

        // A~Z 사전에 추가
		for(int i=0;i<26;i++)
			dic.put(Character.toString((char)(c + i)), i + 1);

사전을 HashMap으로 구현했다.

길이가 1인 모든 단어이므로 A~Z 알파벳 모두를 HashMap의 key로 넣고 value로는 알파벳이 진행될 수록 정수값이 커지도록 색인 번호를 저장하면 된다.

for문으로 char 변수에 A를 시작으로 1씩 더하여 알파벳을 구성하고, for문의 i값으로 색인 번호를 구성했다.

 

 

 

    2.사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.

		for(i=idx;i<n;i++) {
			wc.append(msg.charAt(i));
			if(!dic.containsKey(wc.toString())) 
				break;
			else 
				w = wc.toString();
		}

현재 입력과 일치하는 가장 긴 문자열이 무엇인지 글로만 봤을 때는 한번에 이해하기 어렵다.

입출력 예시2 에서, 처음에는 알파벳 하나씩 w가 됐다가, 다음에는 두세개의 알파벳이 w가 된다.

즉, msg의 문자열을 순서대로 탐색하면서 사전에 존재하는 알파벳 구성이 w가 되는 것이다.

처음엔 알파벳 하나씩밖에 사전에 존재하지 않기 때문에 w가 무조건 한글자가 되지만,

문자열을 돌면서 단계 4에서 단어를 사전에 등록하기 때문에 w가 길어진다.

 

현재 탐색해야 할 인덱스부터, 문자열 끝까지 탐색한다.

문자 하나씩 append 해주면서 그 문자열이 사전에 존재한다면 w에 대입한다.(w는 무조건 사전에 존재해야 하므로)

사전에 존재하지 않는 단어가 있다면 break문으로 빠져나온다.

이때 단계 4를 위해 사전에 존재하지 않는 단어도 따로 저장해두어야 한다.

 

 

    3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.

		list.add(dic.get(w));

단계 2에서 구한 w를 key로, HashMap 형태의 사전에서 검색해 value(색인 번호)를 가져와 list에 저장한다.

입력에서 w를 제거한다는 의미는 다음 탐색에서는 w를 포함하지 않는다는 의미와 같으므로 

함수를 재귀적으로 호출할 때 w의 인덱스 다음부터 전달해주면 된다.

 

 

    4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.

		if(!dic.containsKey(wc.toString()))
			dic.put(wc.toString(), ++last);

단계 2에서 문자를 하나씩 append 해주고, append해준 단어가 사전에 존재하지 않으면 break문으로 빠져나왔다.

존재하지 않은 그 단어는 w와 다음 글자를 더한 것이므로 w+c가 된다.

이w+c를 사전에 추가해준다.

색인 번호는 27을 시작으로 1씩 더해주어야 하므로 현재 사전에 등록된 가장 마지막 색인 번호를 가리키는 변수 하나를 생성해주고,

++연산을 해가며 새로 추가된 단어의 색인 번호를 순차적으로 관리해준다.

(입력에서 처리되지 않은 다음 글자가 남아있지 않은 경우 문자열의 가장 끝을 나타내는 것이므로 w == wc가 같아진다)

 

 

    5. 단계 2로 돌아간다.

		if(i < n)
			compression(i, msg, n);

msg의 문자열을 순서대로 탐색하는 것이므로, 

색인 번호를 출력한 w가 된 인덱스 다음 인덱스부터 다시 탐색하면 된다.

즉, for문으로 w를 생성하고 w+c를 만들었기 때문에 c부터 탐색한다.

for문이 끝났을 때의 i값이 c의 인덱스이기 때문에 i를 인덱스로 전달해 함수를 다시 재귀호출한다.

만약 i가 msg범위를 벗어났다면 호출하지 않고 함수를 끝낸다.

 

 

 

solution에서 이 압축 함수를 호출할 때는 인덱스를 0으로 해두고 한번만 호출하면 된다.

그리고 문자열을 += 해줄 때는 새로운 주소의 String이 할당되기 때문에 굉장히 많은 시간이 소요된다.

즉, String +=보다는 StringBuilder의 append 기능을 활용하자.

아래 사진을 보면 시간 차이가 굉장히 많이 나는 걸 알 수 있다. (상황에 따라 다르겠지만 거의 100배..)

 

 

 

전체 코드

import java.util.*;

class Solution {
    static HashMap<String, Integer> dic = new HashMap<>();
    static ArrayList<Integer> list = new ArrayList<>();
    static int last = 26; // 마지막 색인 번호
    
    public int[] solution(String msg) {
		char c = 'A';

        // A~Z 사전에 추가
		for(int i=0;i<26;i++)
			dic.put(Character.toString((char)(c + i)), i + 1);

		compression(0, msg, msg.length());

		int size = list.size();
		int[] ans = new int[size];

		for(int i=0;i<size;i++)
			ans[i] = list.get(i);
        
		return ans;
	}

	static void compression(int idx, String msg, int n) {
		String w = ""; // 사전에 존재하고 현재 입력과 일치하는 가장 긴 문자열
		StringBuilder wc = new StringBuilder(); // w + 입력에서 처리되지 않은 다음 글자 (c)
		int i;

		for(i=idx;i<n;i++) {
			wc.append(msg.charAt(i));
			if(!dic.containsKey(wc.toString())) 
				break;
			else 
				w = wc.toString();
		}

		list.add(dic.get(w));
		if(!dic.containsKey(wc.toString()))
			dic.put(wc.toString(), ++last);

		if(i < n)
			compression(i, msg, n);
	}
}