[17684] 압축

✔ 압축

[프로그래머스 17684]

문제 분석하기

해시 맵과 투 포인터를 이용해 사전에서 현재 입력과 일치하는 가장 긴 문자열(w)을 찾아 문자열의 색인 번호를 출력하도록 함

그 다음 입력에서 가장 긴 문자열(w)을 제거한 후 다음 글자(c)가 남아있다면 w+c를 사전에 등록하도록 함

이를 반복하여 모든 글자를 압축하도록 함

 

예) ABABABABABABABAB

현재 입력(w)	다음 글자(c)	출력	사전 추가(w+c)
A	B	1	AB:27
B	A	2	BA:28
AB	A	27	ABA:29
ABA	B	29	ABAB:30
BA	B	28	BAB:31
BAB	A	31	BABA:32
ABAB		30
[1, 2, 27, 29, 28, 31, 30]

손으로 풀어보기

1. start 포인터를 0, end 포인터를 start + 1로 선언
2. msg의 start, end만큼 자른 값이 사전에 존재하는 동안, 계속해서 end를 증가시키며 다음 글자까지 사전에 존재하는지 확인
3. 더이상 사전에 존재하지 않는다면 그 글자를 사전에 저장하고, 그 전까지의 글자에 대한 색인 값을 저장
4. 이를 end가 msg의 길이 - 1이 될 때까지 반복한 후 압축된 색인 번호를 반환

슈도코드 작성하기

msg(영문 대문자로만 이뤄진 문자열)
answer(주어진 문자열을 압축한 후의 사전 색인 번호 배열)
list(압축 색인 번호 리스트)
map(영문 대문자를 순서대로 담은 사전 HashMap)
map에 알파벳 대문자 담기 함수(map)
start, end(시작, 끝 투 포인터) = 0, 0
index(사전 저장 인덱스) = 27
while(end가 msg.length보다 작은 동안) {
    end = start + 1
    w(msg의 현재 입력 글자)
    wc(msg의 현재 입력 글자 + 다음 입력 글자) = start부터 end까지 자른 글자로 갱신
    while(map에 wc가 존재하는 동안) {
        w를 wc로 갱신
        end 증가
        if(end가 msg의 길이보다 크다면)
            break
        wc를 msg를 start부터 end까지 자른 글자로 갱신
    }
    list에 w의 색인 저장
    map에 wc와 index++ 저장
    start = end - 1
}
list를 answer 배열에 저장해 반환

map에 알파벳 대문자 담기 함수 {
    c(알파벳) = 'A'
    for(i -> 1부터 26까지) {
        map에 c++와 i을 저장
    }
    map 반환
}

코드 구현하기

/**
 * 17684) 압축
 */
public class L032_17684 {
    // msg(영문 대문자로만 이뤄진 문자열)
    public int[] solution(String msg) {
        // list(압축 색인 번호 리스트)
        List<Integer> list = new ArrayList<>();
        // map(영문 대문자를 순서대로 담은 사전 HashMap)
        Map<String, Integer> map = new HashMap<>();
        // map에 알파벳 대문자 담기 함수(map)
        init(map);
        // start, end(시작, 끝 투 포인터)
        int start = 0, end = 0;
        // index(사전 저장 인덱스)
        int index = 27;
        // end가 msg.length보다 작은 동안
        while (end <= msg.length()) {
            // end = start + 1
            end = start + 1;
            // w(msg의 현재 입력 글자)
            String w = "";
            // wc(msg의 현재 입력 글자 + 다음 입력 글자)
            String wc = msg.substring(start, end);
            // map에 wc가 존재하는 동안
            while (map.containsKey(wc)) {
                // w를 wc로 갱신
                w = wc;
                // end 증가
                end++;
                // end가 msg의 길이보다 크다면
                if (end > msg.length()) {
                    // 종료
                    break;
                }
                // wc를 msg를 start부터 end까지 자른 글자로 갱신
                wc = msg.substring(start, end);
            }
            // list에 w의 색인 저장
            list.add(map.get(w));
            // map에 wc와 index++ 저장
            map.put(wc, index++);
            // start = end - 1
            start = end - 1;
        }
        // answer(주어진 문자열을 압축한 후의 사전 색인 번호 배열)
        int[] answer = new int[list.size()];
        // list를 answer 배열에 저장해 반환
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }

    // map에 알파벳 대문자 담기 함수
    private Map<String, Integer> init(Map<String, Integer> map) {
        // c(알파벳)
        char c = 'A';
        for (int i = 1; i <= 26; i++) {
            // map에 c++와 i을 저장
            map.put(Character.toString(c++), i);
        }
        // map 반환
        return map;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L032_17684 solution = new L032_17684();

        String msg = "KAKAO";

        int[] result = solution.solution(msg);

        System.out.println(Arrays.toString(result));
    }
}