[Programmers] [3차] 압축 (Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/17684

문제

문자열 msg가 주어진다.

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

풀이

특별한 알고리즘이 필요없는 구현 문제이다.
현재 입력과 가장 긴 문자열 w를 찾는 과정에서 인덱스를 잘 조절하는 것이 관건인 것 같다.

사전을 Map<String,Integer> dic으로 정의하여 데이터와 몇번째인지에 대한 정보를 저장했다.

i번째부터 시작하는 문자열 중 현재 dic에 저장되어 있는 가장 긴 문자열을 찾아야 한다.
while문을 이용하여 종료 조건을 dic.containsKey(s+msg.charAt(j))로 설정하여 문자열 s에 문제에서 정의한 w를 저장했다.

		while(j<msg.length() && dic.containsKey(s+msg.charAt(j))) {
                s+=msg.charAt(j);
                j++;
 		}

코드

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        List<Integer> answerList = new ArrayList<>();
        Map<String,Integer> dic = new HashMap<>();
        
        for(int i=0; i<26; i++) {
            dic.put(String.valueOf((char)('A'+i)), i+1);
        }
        
        int idx = 27;
        for(int i=0; i<msg.length();) {
            String s = String.valueOf(msg.charAt(i));
            
            int j = i+1;
            while(j<msg.length() && dic.containsKey(s+msg.charAt(j))) {
                s+=msg.charAt(j);
                j++;
            }
            
            answerList.add(dic.get(s));   
            
            if(j<msg.length()) {
                dic.put(s+msg.charAt(j), idx++);      
            }
            
            i=j;
        }
        
        int[] answer = new int[answerList.size()];
        for (int k = 0; k < answerList.size(); k++) {
            answer[k] = answerList.get(k);
        }
        
        return answer;
    }
}