압축_복습2

문제 풀이

나의 코드

소요 시간: 47분
시간 복잡도: $O(L√L)$

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

class Solution {
    public int[] solution(String msg) {
        int idx = 1;
        Map<String, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for (char c = 'A'; c <= 'Z'; c++) {
            map.put(c + "", idx++);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < msg.length(); i++) {
            String s = sb.toString();
            char c = msg.charAt(i);
            sb.append(c);
            if (!sb.isEmpty() && !map.containsKey(sb.toString())) {
                map.put(sb.toString(), idx++);
                sb.setLength(0);
                sb.append(c);
                list.add(map.get(s));
            }
        }
        if (!sb.isEmpty()) {
            list.add(map.get(sb.toString()));
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

AI 코드

시간 복잡도: $O(L√L)$
코드 분석

전체적인 구조는 동일하나,
StringBuilder 로 구간을 잡고 s 로 이전 값을 저장하는 필요를 없앴다.

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<>();
        for (int i = 0; i < 26; i++) {
            dict.put(String.valueOf((char)('A' + i)), i + 1);
        }
        List<Integer> out = new ArrayList<>();
        int idx = 27;
        int start = 0;
        
        while (start < msg.length()) {
            int end = start + 1;
            while (end < msg.length() && dict.containsKey(msg.substring(start, end + 1))) {
                end++;
            }
            out.add(dict.get(msg.substring(start, end)));
            if (end < msg.length()) {
                dict.put(msg.substring(start, end + 1), idx++);
            }
            start = end;
        }
        return out.stream().mapToInt(Integer::intValue).toArray();
    }
}

문제 풀이 후기

"새로운 글자가 만들어지면 저장 및 삭제 후 배열에 인덱스 삽입"
이라는 규칙을 찾아서 코드로 구현했다.

중간에 다소 헷갈리는 부분이 있었지만, 어제와 다르게 차근차근 주어진 예시를
코드에 대입해가면서 구현이 잘 됐는지, 어떤 부분을 수정해야 하는지 살펴보며
코드를 보완해가며 풀 수 있었다.

설계하는 과정이 반,
해당 설계를 구현해가며 보완하는 것이 나머지 절반이라 생각한다.

AI 코드를 보며 배열의 인덱스를 활용해서 푸니
더 이해하기 간단하다는 생각이 든다.
이런 배열에 관련된 문제에는 나도 인덱스를 활용해서 풀 방법을 먼저
고민해봐야겠다 라는 생각을 했다.