본문 바로가기

알고리즘 풀이/프로그래머스

[프로그래머스] 압축 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA

🔗 문제 링크

[프로그래머스] 압축 / 2018 KAKAO BLIND RECRUITMENT(3차)

 

코딩테스트 연습 - [3차] 압축

TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]

programmers.co.kr

 

📝 풀이 과정

문자열을 반복해서 사전에 넣고 찾는 작업을 해야하고, String(문자열)과 int(색인 번호)를 동시에 저장할 수 있는 Map을 사용하기로 했다. 길이가 1인 문자열을 모두 넣어주기 위해 반복문을 돌며 Map.put 해주었고, 입력 문자열을 하나씩 끊어 반복문을 돌며 탐색하였다.

 

map.containsKey를 통해 만약 현재 key가 사전에 없을 때까지 뒤에 덧붙이는 방식을 사용했다. 사전에 없는 문자열이 나왔다면 반복문을 탈출하고 현재 문자열 - 1은 사전에 존재했기 때문에 그만큼을 사전에서 꺼내 정답 List에 add하고, 없던 문자열은 새롭게 사전에 추가해주었다.

 

💻 코드

import java.util.*;

class Solution {
   public int[] solution(String msg) {
        List<Integer> ans = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();

        // 모든 알파벳을 미리 Map에 넣어둠
        for (int i = 0; i < 26; i++)
            map.put((char) ('A' + i) + "", i + 1);

        char[] arr = msg.toCharArray();
        int idx = 1;
        StringBuilder key = null; // Map에서 찾아볼 String

        while (idx <= msg.length()) {
            // --idx를 통해 이전에 put했던 문자열의 마지막 인덱스부터 시작
            key = new StringBuilder(arr[--idx] + "");

            while (++idx < msg.length() && map.containsKey(key.toString()))
                key.append(arr[idx]);

            // 이미 Map에 존재하면 key에 덧붙이고 없다면 새로 사전에 등록해야 하기때문에 탈출
            if (idx == msg.length() && map.containsKey(key.toString()))
                break;

            ans.add(map.get(key.substring(0, key.length() - 1))); // 마지막에 없던거 나왔으니까 뒤에거 자르고 답에 추가
            map.put(key.toString(), map.size() + 1); // 없던거 사전에 추가
        }
        ans.add(map.get(key.toString()));

        return ans.stream().mapToInt(i -> i).toArray(); // List<Integer> to int array
    }
}