문제

문제 링크

접근

• 투 포인트를 이용한 문자열 분리와 해싱을 통해 해결하였다.
• 한글자 단위로는 다 해싱이 되어 있으므로, 두 글자 이상부터 해당 문자열이 사전에 포함되어 있는지 확인한다. 이때 점점 늘려가다가, 없는 순간의 바로 앞칸을 이용하여 최장 길이를 찾는다.
• 반복문 종료 조건을 end 인덱스로 잡는다면, 마지막까지 한 칸의 단어가 사전에 포함되어 있다는 것이기 때문에 해당 문자열 관련해서도 처리한다.

풀이

import java.util.*;

class Solution {
    public List<Integer> solution(String msg) {
        List<Integer> ans = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        int idx = 27;
        
        for (int i = 0; i < 26; i++)
            map.put((char)('A' + i) + "", i+1);
        
        int start = 0, end = 2;
        while(end <= msg.length()) {
            String curr = msg.substring(start, end);
            
            if (map.containsKey(curr)) {
                end++;
                continue;
            }
            
            ans.add(map.get(msg.substring(start, end-1)));
            map.put(curr, idx++);
            start += (end - start - 1);
            end++;
        }
        
        ans.add(map.get(msg.substring(start, end-1)));
        
        return ans;
    }
}