[프로그래머스 코테 연습]자바 - 3차 압축

개요

코딩테스트 연습 - [3차] 압축 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

난이도 : 레벨 2

특징 : 2018 KAKAO BLIND RECRUITMENT 기출 문제

 

이 문제는 처음 딱 봤을 땐, 어려워 보였는데 막상 풀다보니 헷갈리는 점 제외하면 딱히 막힌다는 느낌은 받지 못한 문제였습니다.

 

다만, 풀다가 조건을 잘못 읽어서 몇번이나 다시 읽었는지 몰랐네요..

 

문제를 자세히 확인하는 버릇을 들어야겠다고 생각했습니다.

풀이법

import java.util.*;

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

        for (int i = 0; i < 26; i++){
            char temp = (char) ('A' + i);
            map.put(String.valueOf(temp),i+1);
        }

        int lastMapIndex = 26;
        int startMsgIndex = 0;
        int msgLength = msg.length();

        while(startMsgIndex < msgLength){
            StringBuilder word = new StringBuilder();
            word.append(msg.charAt(startMsgIndex));
            int endMsgIndex = startMsgIndex + 1;

            while(endMsgIndex < msgLength && map.containsKey(word.toString() + msg.charAt(endMsgIndex))){
                word.append(msg.charAt(endMsgIndex));
                endMsgIndex++;
            }

            results.add(map.get(word.toString()));

            if (endMsgIndex < msgLength){
                map.put(word.toString() + msg.charAt(endMsgIndex), ++lastMapIndex);
            }


            startMsgIndex = endMsgIndex;
        }
        
        int[] answer = new int[results.size()];
        for (int i = 0; i < results.size(); i++) {
            answer[i] = results.get(i);
        }

        return answer;
    }
}

중점포인트

1. HashMap을 사용하여 사전 구성

 

2. 현재 단어 w를 구성하기 위해 stargMsgIndex, endMsgIndex 두 인덱스를 가리키는 일종의 포인터를 사용

 

과정

1. 사전에 A ~ Z 까지 기본적인 알파벳을 초기화해준다 + 단어 w의 시작점을 가리키는 startMsgIndex와 사전의 마지막 값이 가리키는 숫자를 말하는 lastMapIndex를 초기화한다.

 

2. startMsgIndex가 가리키는 문자를 word 라는 변수에 저장한다. (이때, StringBuilder를 사용하여 String 값을 구성한다)

또한, endMsgIndex는 startMsgIndex + 1로 넣어준다. (다음 문자를 확인해야하므로)

 

3. endMsgIndex가 전체 단어의 길이를 초과하는지와 다음 단어를 포함하여 사전에 있는지를 반복문을 사용해 검사한다.

이때, 다음 단어가 포함이 되어있다면 endMsgIndex++를 하고, 현재 단어인 word에 그 문자를 추가한다.

 

4. 결과를 저장한다.(다음 단어를 포함하여 계속 검사를 진행했으므로 word는 최종적으로 사전에 있는 값이 된다)

 

5. endMsgIndex를 startMsgIndex를 바꿔주고 다시 2로 돌아간다.