[알고리즘] 프로그래머스 [3차] 압축 (2018 KAKAO BLIND RECRUITMENT) -해시, 맵- 자바

 

 

https://programmers.co.kr/learn/courses/30/lessons/17684?language=java 

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

 

 

 

알고리즘 그만보고싶어... 개발이 나아..

 

 

오랜만의 알고리즘 풀이입니다. ㅎㅎ 오늘은 프로그래머스의 Level2 문제인 압축이라는 문제를 풀어봤습니다. 처음 문제를 보자마자 HashMap을 사용해야겠다고 생각해서 빠르게 접근할 수 있었습니다.

 

저의 풀이방법을 요약하면 다음과 같습니다. 

1. 현재까지의 입력 단어 w 를 받는다.

2. w의 압축번호 계산 

3. w+c 도 색인에 있는지 검색해본다. 있는경우 더 좋게 압축할 수 있으므로 지금까지 작업을 continue로 건너뛰고 지금까지의 현재단어에서 재탐색한다. -> 1로 되돌아감

4. 3번에서 w+c가 색인에 없는 경우 현재 단어 w의 압축번호를 정답리스트에 추가하고 그 다음단어 c와 합친 wc를 색인에 추가해준다.

 

 

자세한 사항은 주석으로 적어놨습니다. 

풀이는 다음과 같습니다. 

 

[Java]

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

class Solution {
    Map<String, Integer> map = new HashMap<>();
    List<Integer> answerList = new ArrayList<>();

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution("TOBEORNOTTOBEORTOBEORNOT");
    }

    public int[] solution(String msg) {
        int[] answer = {};
        int index = 0;
        initMap();
        String w = ""; // 현재입력
        String c = ""; // 다음글자
        int num = 0; // 압축번호
        for (int i = 0; i < msg.length(); i++) {
            w += msg.charAt(i); // 현재 글자
            num = cal(w); // 압축번호 계산
            if (i + 1 < msg.length()) { // 뒤에 문자남은 경우
                c = "" + msg.charAt(i + 1);
                String wc = w + c;
                if (cal(wc) != -1) { // w+c 가 사전에 있는 경우 더 최적가능하므로 이어서 탐색
                    continue;
                }
                w = wc; // 사전추가(w+c) 만들어줌
            }
            answerList.add(num); // 정답 세팅
            addMap(w); // 색인번호 추가
            w = ""; //초기화
        }
        answer = new int[answerList.size()];
        for (int i=0; i<answer.length; i++){
            answer[i] = answerList.get(i);
        }
        return answer;
    }

    // map 초기화
    private void initMap() {
        char c = 'A';
        for (int i = 1; i <= 26; i++) {
            map.put(c + "", i);
            c++;
        }
    }

    // 해당 단어 색인번호 추출
    private int cal(String str) {
        int num = -1;
        if (map.containsKey(str)) {
            num = map.get(str);
        }
        return num;
    }

    // 사전추가
    private void addMap(String str) {
        map.put(str, map.size() + 1);
    }

}

https://github.com/mtjin/algorithm_practice/commit/63713d2c6fc9649eca9252282615644c51e7e3ef

프로그래머스 압축 풀이 · mtjin/algorithm_practice@63713d2

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!!