문제
programmers.co.kr/learn/courses/30/lessons/17684
설명
LZW 압축은 다음 과정을 거친다.
- 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
- 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
- w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
- 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
- 단계 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
'알고리즘 문제 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 - Java] 삼각 달팽이(월간 코드 챌린지 시즌1) (0) | 2020.09.22 |
---|---|
[프로그래머스 - Java] 두 개 뽑아서 더하기(월간 코드 챌린지 시즌1) (0) | 2020.09.22 |
[프로그래머스 - Java] 점프와 순간 이동 (0) | 2020.09.10 |
[프로그래머스 - Java] 단어 변환 (DFS/BFS Level 3) (0) | 2020.05.19 |
[프로그래머스 - Java] 비밀지도(2018 KAKAO BLIND RECRUITMENT [1차]) (0) | 2020.05.03 |
댓글