프로그래머스 lv2 - 압축 (자바) [2018 KAKAO BLIND RECRUITMENT]

문제

---

프로그래머스 lv2 - 압축

풀이

---

알고리즘이라기 보다는 자료구조를 잘 사용할 줄 알아야 하는 문제

< 내 풀이 >

• 색인 번호와 그에 맞는 문자열을 hashmap에 저장
• msg의 문자마자 그 다음 문자, 그 다음 문자... 마지막문자까지 더해가며 더 긴 문자열이 사전에 있는지 체크
  -> 더 긴 문자열이 있다면 가장 긴 길이의 문자열, 그 문자열의 길이, 그 문자열의 끝부분의 인덱스 갱신
• 그 다음 순서로 오는 문자들을 다 더해가며 가장 긴 문자열을 찾았다면 그 문자열을 답에 추가하고 msg에서 삭제
  -> 문자열을 msg에서 삭제할 때 substring() 사용

어려웠던 점

---

순차적으로 다음 문자를 더해가며 사전에 있는지 체크할 때 사전에 있으면 거기서 그것보다 긴 문자열은 없다고 판단하여 탐색을 종료했다. 그랬더니 반복문이 끝나지 않는 문제가 발생해서 시간을 배로 소비했다.

예시를 다시 자세히 보니 TO가 사전에 있어도 그 다음인 TOB가사전에 존재하여 가장 긴 문자열이 TOB가 될 수 있는 예시를 확인하여 코드를 수정했다.

코드

---

내 풀이 ( 코드가 별로 맘에 들지 않음 )

import java.util.*;
class Solution {
    public ArrayList<Integer> solution(String msg) {
        ArrayList<Integer> ret = new ArrayList<>();
        HashMap<String, Integer> hm = new HashMap<>();
        int index = 0; // 색인 번호
        for (int i = 'A'; i <= 'Z'; i++)
            hm.put(String.valueOf((char)i), ++index);

        while (msg.length() > 0) {
            String init = String.valueOf(msg.charAt(0));
            String str = init;
            String max_str = str;
            int max_length = 1;
            int max_str_idx = 0;
            for (int j = 1; j < msg.length(); j++) {
                str += msg.charAt(j); // 다음 글자 추가
                if (hm.containsKey(str) && max_length < str.length()) {
                    max_str = str;
                    max_length = str.length();
                    max_str_idx = j;
                }
            }
            ret.add(hm.get(max_str));
            if (max_str_idx < msg.length() - 1)
                hm.put(max_str + msg.charAt(max_str_idx + 1), ++index);
            msg = msg.substring(max_str.length());
        }

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

        return ret;
    }
}

다른 풀이 ( 코드가 훨씬 간결한 코드 )

import java.util.*;
class Solution {
    public ArrayList<Integer> solution(String msg) {
        int[] answer = {};
        ArrayList<Integer> ans = new ArrayList<Integer>();
        int ind = 1; 
        HashMap<String, Integer> hs = new HashMap<String,Integer>();
        for(char i = 'A'; i<='Z'; i++){
            hs.put(i+"",ind++);
        }
        int size = msg.length();
        for(int i =0; i< size; i++){
            int a = 1;
            while(i+a<=size && hs.containsKey(msg.substring(i,i+a))){
                a++;
            }
            if(i+a>size){
                ans.add(hs.get(msg.substring(i)));
                break;
            }
            ans.add(hs.get(msg.substring(i,i+a-1)));
            hs.put(msg.substring(i,i+a),ind++);
            if(a>1)i+=a-2;
        }
        return ans;
    }
}

참고

---

내 풀이가 아닌 다른 풀이는 프로그래머스 다른 사람의 풀이 중 좋다고 생각되는 코드를 참고하였음