압축_복습

2026.09.01

문제 풀이

나의 코드

---

소요 시간: 2시간 16분
시간 복잡도: $O(n)$

---

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(String msg) {
        int order = 1;
        Map <String, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        
        for (char c = 'A'; c <= 'Z'; c++) { // 해시맵에 알파벳 저장
            map.put(Character.toString(c), order++);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < msg.length(); i++) {
            char c = msg.charAt(i);
            sb.append(c);
            if (map.get(sb.toString()) == null) { // 해시맵에 해당 단어가 존재하지 않을 때
                map.put(sb.toString(), order++);
                list.add(map.get(sb.substring(0, sb.length() - 1)));
                sb.setLength(0);
                sb.append(c);
            }
        }
        if (sb.length() > 0) {
            list.add(map.get(sb.toString()));
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

AI 코드

---

시간 복잡도: $O(n)$

---

코드 분석

substring 대신에 prev, cur 변수를 이용하여
반복당 문자열 객체 1개 생성을 감소하였다.

---

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(String msg) {
        Map<String, Integer> dict = new HashMap<>();
        int index = 1;
        for (char c = 'A'; c <= 'Z'; c++) { // 사전 초기화
            dict.put(String.valueOf(c), index++);
        }

        List<Integer> answer = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int prev = 0; // 직전까지 매칭된 문자열의 색인

        for (int i = 0; i < msg.length(); i++) {
            char c = msg.charAt(i);
            sb.append(c);
            Integer cur = dict.get(sb.toString());

            if (cur == null) {          // 사전에 없음 → 등록하고 직전 색인 출력
                dict.put(sb.toString(), index++);
                answer.add(prev);
                sb.setLength(0);
                sb.append(c);           // 마지막 글자부터 다시 시작
                prev = dict.get(sb.toString());
            } else {                    // 사전에 있음 → 색인만 갱신하고 계속 확장
                prev = cur;
            }
        }
        answer.add(prev);               // 남은 문자열 처리

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

문제 풀이 후기

이전에는 풀었던 문제임에도 불구하고 이번에는 해결하지 못하였다.

프로젝트의 막바지라 약 2주동안 코딩 테스트를 쉬었던 상태에서 시작해서
감을 잃었나 싶다. 역시 뭐든 꾸준히 하는 것이 가장 중요하다고 생각된다.