[프로그래머스(Programmers)] [3차]압축 (java) /2018 KAKAO BLIND RECRUITMENT

안녕하세요. 오늘은 프로그래머스의 [3차] 압축 문제를 풀어보겠습니다. 이 문제는 2018년 KAKAO BLIND RECRUITMENT에서 출제되었습니다.

1) 문제 링크

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

2) 문제 풀이

✔ 기본 색인 생성(HashMap 이용)

색인 관리에는 HashMap을 사용합니다. HashMap의 Key는 색인 단어(String)이고, 색인 번호는 value가 됩니다. 아스키코드를 이용해서 알파벳 A부터 Z까지 기본적인 색인을 만들어줍니다.

✔ 압축 함수 작성

LZW알고리즘을 이용하여 문자열을 압축하는 함수를 작성합니다. 이 때 이 함수의 로직 순서는 아래와 같습니다.

1. i번째 String A에서

• 1-1. 색인(HashMap)에 A가 있으면
  -> 새로운 String B = (i번째 String) + (i+1번째 String)
  -> A에 B 대입
  -> 1로 돌아감 (색인에 A가 없을 때까지 반복)
• 1-2. 색인(HashMap)에 A가 없으면
  -> A의 색인번호를 answer list에 저장
  -> B를 새 색인번호로 hashMap에 등록

✔ msg의 마지막 index 주의하기

주어진 msg의 마지막 index에서 주의할 점이 있습니다. 마지막 index i에서 i를 포함하지 않는 String을 A라고 하고, i를 포함하는 새로운 String을 B라고 합시다.(위의 압축로직을 잘 생각해보면 마지막부분에선 A와 B가 지금 설명한 것처럼 만들어집니다!)

• 2-1. 새로운 String B가 색인(HashMap)에 있으면
  -> B를 색인에 저장하지 않는다
  -> B의 색인번호를 answer list에 저장
• 2-2. 새로운 String B가 색인에 없으면
  -> B를 색인에 저장
  -> A의 색인번호를 answer list에 저장

3) 전체 코드

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        Map<String, Integer> index = makeBasicIndex();
        String[] arr = msg.split("");
        
        List<Integer> answer = compress(index, arr);
        
        return listToArray(answer);
    }
    
    //기본 색인 생성(A ~ z) 65 ~ 90
    private Map<String, Integer> makeBasicIndex() {
        Map<String, Integer> index = new HashMap<>();
        
        for(int i = 65; i <= 90; i++) {
            index.put(Character.toString((char) i), i - 64);
        }
        
        return index;
    }
    
    private List<Integer> compress(Map<String, Integer> index, String[] arr) {
        List<Integer> answer = new ArrayList<>();
        int length = arr.length;
        
        for(int i = 0; i < length; i++) {
            StringBuilder sb = new StringBuilder();
            
            if(i >= length - 1) {
                answer.add(index.get(arr[i]));
                break;
            }
            
            while(i < length) {
                sb.append(arr[i]);
                if(index.containsKey(sb.toString())) {
                    i++;
                } else {
                    break;
                }
            }
            
            //while 결과
            //sb에 있는 값 = index에 새로 추가해야 할 값
            //sb - 맨 끝자리 = index에서 찾아서 value answer list에 추가
            if(!index.containsKey(sb.toString())) {
                index.put(sb.toString(), index.size() + 1);
            }
            
            if(i != length) {
                sb.deleteCharAt(sb.length() - 1);
            }
            
            answer.add(index.get(sb.toString()));
            i--;
        }
        
        return answer;
    }
    
    private int[] listToArray(List<Integer> list) {
        int[] array = new int[list.size()];
        int idx = 0;
        for(int num : list) {
            array[idx] = num;
            idx++;
        }
        
        return array;
    }
}

4) 느낀점

항상 문제를 풀 때 테스트케이스를 찾지 못하고, 코드가 틀린 이유를 찾지 못해서 애를 먹었었다. 그런에 이번에는 혼자서 틀린 이유를 찾아냈다.! 문제를 풀 때 무작정 코드부터 작성하지 말고, 천천히 종이에 로직을 적어보는게 도움이 많이 된다.
msg의 마지막부분에 대한 처리에서 조금 애를 먹었는데, 무조건 index HashMap에 값을 넣지 말고 존재여부에 따라 없을때만 집어넣었더니 문제가 해결됐다.