[프로그래머스] 압축 (Java)

문제

프로그래머스

 

알고리즘

해시맵

 

풀이

해시맵으로 사전을 구현한다.

"A": 1, "B":2 ,..., "Z": 26 으로 해시맵을 초기화하고, 사전의 다음 색인 번호를 나타낼 index를 27로 초기화한다.

 

msg가 빈 문자열이 될 때까지

1. w를 얻는다.

- 문자열을 탐색하며 해시맵에 없는 문자열이 나올 때까지 문자열에 문자를 하나씩 붙인다.

 

2. 해시맵에서 w의 value를 찾아 answer에 삽입한다.

3. msg에서 w를 삭제한다.

4. 문자열이 남아있다면 첫 글자를 w에 추가하여 index를 value로 해시맵에 삽입하고 index를 1 늘린다.

 

문자열을 수정하는 연산이 많기 때문에 StringBuilder를 사용한다.

 

 

코드

import java.util.*;

class Solution {
    public ArrayList<Integer> solution(String msg) {
        ArrayList<Integer> answer = new ArrayList<>();
        
        Map<String, Integer> map = new HashMap<>();
        for(int i=1; i<=26; i++) {
            map.put(String.valueOf((char)('A' + i - 1)), i);
        }
        
        int index = 27;
        StringBuilder sb = new StringBuilder(msg);
        StringBuilder longest = new StringBuilder();
        int count = 0;
        while(sb.length() > 0) {
            StringBuilder w = getW(sb, map);
            answer.add(map.get(w.toString()));
            sb.delete(0, w.length());
            
            if(sb.length() > 0)
                map.put(w.append(sb.charAt(0)).toString(), index++);
        }
        
        return answer;
    }
    
    public StringBuilder getW(StringBuilder sb, Map<String, Integer> map) {
        StringBuilder w = new StringBuilder();
        
        for(int i=1; i<=sb.length(); i++) {
            if(map.containsKey(sb.substring(0, i)))
                w.append(sb.charAt(i-1));
            else break;
        }
        
        return w;
    }
}