[프로그래머스][Level2] 압축 - JAVA

[문제 설명]

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

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

 

[풀이 과정]

특별한 알고리즘을 이용하기보다는 그냥 문제에 주어진 규칙을 따라가며 풀었다. 

 

단어가 사전에 들어가는 규칙이 있는데, 

만약 "KAO" 라는 단어가 사전에 들어간다고 하면, "K" 와 "KA" 는 이미 사전에 존재한다. 

때문에 "K"부터 뒤에 한 단어씩 늘리면서 사전에 있는지 탐색하다가 사전에 없는 단어 S까지 도달하면 아래 작업을 하면 된다. 

1.  단어 S를 사전에 넣는다. 사전에 없는 단어이므로..

2. 단어 S에서 뒤에 한글자를 뺀다. 그리고 answer 배열에 해당 글자 색인 번호를 add한다. 

 

[JAVA code]

package com.algorithm.level2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Test35 {
    public static void main(String[] args) {
        solution("ABABABABABABABAB");
    }

    public static int[] solution(String msg) {
        List<Integer> answerList = new ArrayList<>();

        // 사전 HashMap으로 구현
        // 사전 초기화
        HashMap<Integer, String> dictionary = new HashMap<>();
        for (int i = 1; i <= 26; i++) {
            dictionary.put(i, String.valueOf((char) (i + 64)));
        }

        // 단어를 순회할 index
        int index = 0;
        while (index < msg.length()) {
            // 단어의 해당 인덱스 문자
            String w = msg.substring(index, index + 1);

            // w를 시작으로 글자를 하나씩 늘려감
            for (int i = index + 1; i < msg.length(); i++) {
                w += msg.charAt(i);

                // 사전에 포함하고 있지 않는 단어까지 도착하면
                if (!dictionary.containsValue(w)) {
                    // 사전에 해당 단어 put
                    dictionary.put(dictionary.size() + 1, w);

                    // 단어에서 다시 마지막 글자를 제거
                    w = w.substring(0, w.length() - 1);
                    break;
                }
            }
            // answer에 단어 w add
            answerList.add(getKey(dictionary, w));

            // 다음에 순회할 index
            index = index + w.length();
        }

        int count = 0;
        int[] answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[count++] = answerList.get(i);
        }
        return answer;
    }

    // hashMap에서 value로 key 찾기
    public static int getKey(HashMap<Integer, String> m, Object value) {
        for (int o : m.keySet()) {
            if (m.get(o).equals(value)) {
                return o;
            }
        }
        return 0;
    }
}

 

// 2021-07-14 : 두번째 풀이

첫번째 풀 때보다 코드 길이가 길어졌다. 

요즘은 문제의 요구사항을 잘게 나누어 메소드화시키는 코드 스타일로 변해가고 있다. 

이유인즉슨.. 회사에서 개발하는 습관이 코테에서도 발현되다보니 그런 것 같다.

package com.algorithm.kakaoTest.two;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Test02 {
    public static void main(String[] args) {
        String msg = "TOBEORNOTTOBEORTOBEORNOT";
        int[] answer = solution(msg);
        System.out.println(Arrays.toString(answer));
    }

    public static HashMap<String, Integer> dictionaryMap = new HashMap<>();

    public static int[] solution(String msg) {
        List<Integer> answerList = new ArrayList<>();
        dictionaryMap = initDictionaryMap(); // 1. 사전 초기화

        while (true) {
            String w = getLongestWords(msg); // 2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다
            answerList.add(dictionaryMap.get(w)); // w에 해당하는 사전의 색인 번호를 출력
            msg = removeW(w, msg); // 입력에서 w를 제거

            if (msg.length() == 0) { // w를 제거한 뒤 msg가 모두 제거되면 종료
                break;
            }

            String c = msg.charAt(0) + ""; // 입력에서 처리되지 않은 다음 글자
            String newWords = w + c;
            dictionaryMap.put(newWords, dictionaryMap.size() + 1); // 3. w+c에 해당하는 단어를 사전에 등록
        }

        int[] answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }
        return answer;
    }

    public static HashMap<String, Integer> initDictionaryMap() {
        for (int i = 1; i <= 26; i++) {
            char c = (char) (i + 64);
            dictionaryMap.put(String.valueOf(c), i);
        }
        return dictionaryMap;
    }

    public static String getLongestWords(String curMsg) {
        for (int i = curMsg.length(); i >= 0; i--) {
            String s = curMsg.substring(0, i);
            if (dictionaryMap.containsKey(s)) {
                return s;
            }
        }
        return "";
    }

    public static String removeW(String w, String curMsg) {
        int wLength = w.length();
        curMsg = curMsg.substring(wLength);
        return curMsg;
    }
}