(Java) 프로그래머스 - 압축

문제를 이해하는데 은근히 시간이 걸린 문제였다.

특별한 알고리즘이 필요한것도 아닌 구현 문제였는데 

조건도 까다롭다고 느껴져서 한번에 풀지 못하고 몇번 막혀서 고민하는 시간이 많았다.

처음 풀이도 정답으로 인정되었지만 깨끗하게 풀지 못한것 같아서 리펙터링을 한번 했다.

 

로직은 A부터 Z까지 번호를 부여해서 HashMap에 넣어준다.

그리고 i번째 글자를 빈 String에 추가하고 만들어진 글자가 사전에 있을때까지 i + 1 글자를 추가하고 탐색을 끝낸다.

만들어진 글자 - 1 만큼 인덱스를 조정하고 결과 리스트에 추가하고 다음 글자로 넘어간다.

 

말로 설명하니 더 복잡한것 같은데 코드로 보면 오히려 간단하다.

---

처음 코드

import java.util.*;
class Solution {
    public int[] solution(String msg) {
    
    	// 결과를 담을 리스트
        List<Integer> list = new ArrayList<>();

        // 사전을 담을 map 생성
        Map<String, Integer> map = new HashMap<>();

        // map 초기화
        int n = 1;
        char ch = 'A';
        for (int i = 0; i < 26; i++) {
            map.put(String.valueOf(ch++), n++);
        }
		
        // 사전 번호
        int start = 27;
        
        // 문자열 탐색
        roof : for (int i = 0; i < msg.length(); i++) {
            StringBuilder sb = new StringBuilder();
            char w = msg.charAt(i);
            sb.append(w);
            int cnt = 1;

            while (map.containsKey(sb.toString())) {
                int idx = i + cnt;
                if (idx >= msg.length()) {
                    list.add(map.get(sb.toString()));
                    break roof;
                }
                sb.append(msg.charAt(idx));
                cnt++;
            }
            map.put(sb.toString(), start++);
            if (sb.length() > 2) {
                i += cnt - 2;
            }

            list.add(map.get(sb.delete(sb.length() - 1, sb.length()).toString()));
        }
		
        // 리스트 배열에 복사
        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 int[] solution(String msg) {
        // 사전 번호를 담을 list
        List<Integer> list = new ArrayList<>();

        // 사전을 담을 map 생성
        Map<String, Integer> map = new HashMap<>();

        // map 초기화
        char ch = 'A';
        for (int i = 0; i < 26; i++) {
            map.put(String.valueOf(ch++), i + 1);
        }

        // 사전 번호
        int idx = 27;

        for (int i = 0; i < msg.length(); i++) {
            String s = "";
            // i번째 글자 추가
            s += msg.charAt(i);
            // i + 1 글자 추가
            for (int j = i + 1; j < msg.length(); j++) {
                // 추가한 글자가 사전에 없다면
                if (!map.containsKey(s + msg.charAt(j))) {
                    // 사전에 추가하고 탐색 중단
                    map.put(s + msg.charAt(j), idx++);
                    break;
                    // 사전에 있다면 없을때까지 한 글자씩 추가
                } else {
                    s += msg.charAt(j);
                }
            }
            // 인덱스 조정
            i += s.length() - 1;
            // 번호 리스트에 저장
            list.add(map.get(s));
        }
        
        // list를 배열에 복사
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
}