[프로그래머스] 압축

프로그래머스

2018 KAKAO BLIND RECRUITMENT

 

프로그래머스

[3차] 압축

 

문제 정리

1. 어피치가 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. -> LZW압축 알고리즘
2. 길이가 1인 모든 단어를 포함하도록 사전을 초기화
3. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
4. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w제거
5. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록
6. (3)번과정으로 돌아간다.

 

시작하기 전 접근 방법

1. 입력 받을 영문과 해당 영문에 해당하는 사전 번호를 저장할 HashMap과 번호를 순차적으로 계속 저장할 ArrayList를 만든다.
2. 기본 베이스 알파벳을 1~26번을 알파벳과 쌍으로 hashMap에 저장한다.
3. 매개변수 msg문자열을 인덱스 0부터 마지막까지 순차적으로 반복하고 반복하면서 저장할 문자열 변수(w)를 만든다.
4. 현재 문자와 다음 문자를 합친 문자열이 hashMap에 없다면 list에 현재 문자에 해당하는 번호를 리스트에 추가한다.
5. 문자열이 hashMap에 있다면 문자열(w)에 추가한 문자를 만든다. 현재 인덱스 값도 리스트에 추가한다.
6. 매개변수 문자열이 끝날때까지 새로운 단어를 map에 인덱스와 함께 추가한다.
7. List에 저장한 번호를 return 값이 배열이기 때문에 배열로 바꿔 return 한다.

 

테스트 예제 값

 

 

 

 

1. 사전 번호를 단어와 번호를 쌍으로 저장할 hashMap과 출력 번호를 저장할 ArrayList를 만든다.

HashMap<String, Integer> map = new HashMap<>();
ArrayList<Integer> list = new ArrayList<>();

 

 

2. 기본 알파벳을 1번부터 26번까지 순차적으로 map에 저장한다. 

int index = 1;
for (int i = 'A'; i <= 'Z'; i++) {
	map.put(String.valueOf((char) i), index++);
}

 

 

3~6번 과정 반복문을 이용하여 매개변수 msg인덱스가 마지막까지 반복하면서 사전을 만든 map에 key값이 없다면 w에 해당하는 번호를 리스트에 저장하고 key값이 존재할 경우 map에서 value 값을 가져와 list에 저장한다.
앞단어와 다음 단어를 조합했을 때 없으면 앞단어에 해당하는 value 값을 가져오고 앞뒤단어를 조합한 단어를 map에 idx값과 단어를 쌍을 이뤄 저장하고 해당 idx 값을 list에 저장한다.

int idx = 0;
while (idx < msg.length()) {
	String w = "";
	while (idx < msg.length()) {
		if (!map.containsKey(w + msg.charAt(idx))) {
			break;
		} else {
			w += msg.charAt(idx);
		}
		idx++;
	}
	list.add(map.get(w));
	if (idx < msg.length()) {
		map.put(w + msg.charAt(idx), index++);
	}
}

 

 

7. ArrayList에 저장되어 있는 번호를 int[]배열로 return 해야 하기 때문에 리스트에 있는 값을 반복문을 이용하여 옮긴다.

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

 

 

최종 코드

import java.util.*;

public class Solution {
	public int[] solution(String msg) {
        
		HashMap<String, Integer> map = new HashMap<>();
		ArrayList<Integer> list = new ArrayList<>();
		int index = 1;
		for (int i = 'A'; i <= 'Z'; i++) {
			map.put(String.valueOf((char) i), index++);
		}
		int idx = 0;
		while (idx < msg.length()) {
			String w = "";
			while (idx < msg.length()) {
				if (!map.containsKey(w + msg.charAt(idx))) {
					break;
				} else {
					w += msg.charAt(idx);
				}
				idx++;
			}
			list.add(map.get(w));
			if (idx < msg.length()) {
				map.put(w + msg.charAt(idx), index++);
			}
		}

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

 

문제점

처음 코드를 작성할 때는 새로운 단어를 만들 때 map에 저장하는 방법으로 진행했다. 문제를 제대로 읽지 않고 오해를 해서 발생한 문제였다. 앞단어가 존재하고 다음 단어가 존재하지 않을 때 앞단어에 해당하는 사전번호를 List에 저장하고 다음 단어정보를 사전에 저장하고 번호도 List에 저장하는 압축 알고리즘을 구현했어야 했다.

앞뒤 과정을 생각하지 않고 새로운 단어에 대한 사전 저장 출력 접근만 생각하면 테스트 코드 1번은 완성되지만 다른 테스트 코드는 원하는 결과 값이 나오지 않는다.