[java] 프로그래머스 - 압축

 

📖 풀이한 문제

• 프로그래머스 - 압축

---

💡 문제에서 사용된 알고리즘

• HashMap

---

📜 코드 설명

• map을 사전처럼 사용 (key : 단어, value : 색인 번호)
• 변수 idx : 사전에 색인번호
• 처음에 map에 A - Z까지의 idx를 넣어준다.
• 리스트 list : answer에 해당하는 색인번호를 넣을 리스트
• for문: w 찾기 시작하는 반복문
• while문 : w를 완성하는 반복문
• 반복문을 사용하여 단어를 탐색한다. for문안에 while문에서 다음 문자를 붙인 단어가 map에 있더라면 현재 문자(now)에 다음 문자를 붙여주고 사전에 없더라면 다음 문자를 붙인 단어를 map에 넣어준다. for문에 i가 맨 마지막이라면 다음 문자가 없으므로 그 점을 유의해준다.
• while 반복문이 끝난 후 사전에 들어있는 now의 색인번호를 리스트에 넣어준다.

프로그래머스

 

 

📜 코드 

import java.util.*;

public class 압축 {
    public int[] solution(String msg) {
        // map을 사전처럼 사용
        // key : 단어, value : 인덱스
        HashMap<String, Integer> map = new
            HashMap<>();

        // 사전에 해당하는  인덱스
        int idx = 1;

        // A - Z까지의 인덱스를 map에 입력
        for (char c = 'A'; c <= 'Z'; c++) {
            map.put(c + "", idx++);
        }

        int len = msg.length();

        // list에는 answer에 해당하는 색인 번호 출력
        ArrayList <Integer> list = new ArrayList<>();

        // msg를 단어 탐색
        for (int i = 0; i < len; i++) {
            // 현재 사전에서 찾을 수 있는 가장 긴 문자열 w
            String now = msg.charAt(i) + "";

            // 현재 문자에 다음 문자를 붙이면서 map에 들어있는지 확인한다.
            // 들어있더라면 현재 now에 다음 문자를 붙여주고
            // 아니라면 map에 다음 문자까지 붙여서 문자와 인덱스를 넣어준다. 반복문 종료
            // 현재 인덱스가 끝일 경우도 생각해준다.
            while (true) {
                if (i != len - 1 && map.containsKey(now + msg.charAt(i + 1))) {
                    now += msg.charAt(++i);
                } else if (i != len - 1) {
                    map.put(now + msg.charAt(i + 1) , idx++);
                    break;
                } else break;
            }

            // 현재 찾은 w의 색인 번호를 리스트에 넣어준다.
            list.add(map.get(now));


        }

        // 리스트에 값들을 answer 배열에 넣어준다.
        int answerIdx = 0;
        int[] answer = new int [list.size()];
        for (Integer i : list) {
            answer[answerIdx++] = i;
        }
        return answer;
    }
}