[프로그래머스/Level2] [3차] 압축 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• Map

 

문제에서 말한 순서대로 진행하면 된다.

 

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.

→ 사전 Map에 알파벳 대문자와 색인 번호를 1~26번까지 저장한다.

2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다. (바깥쪽 while문)
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다. (안쪽 while문)
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.

if(idx < msg.length()) {    // w + c
    map.put(str + msg.charAt(idx), map.size() + 1);
}

5. 단계 2로 돌아간다.

 

 

 

[ 진행 과정 ] 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = sol.solution("KAKAO");
        
        for(int i : arr)
            System.out.print(i + " ");
        System.out.println();
    }
}
 
class Solution {
    public int[] solution(String msg) {
        
        List<Integer> list = new ArrayList<>();
        
        HashMap<String, Integer> map = new HashMap<>(); // 사전
        
        // [단계1] 길이가 1인 모든 단어 포함하도록 사전 초기화 : 'A'부터 'Z'까지 저장하기
        for(int i = 1 ; i <= 26 ; i++) {
            map.put(String.valueOf((char)('A' + i - 1)), i);
        }
 
        int idx = 0;
        
        // [단계2] 현재 입력과 일치하는 가장 긴 문자열 w 찾기
        while(idx < msg.length()) {
            String str = "";
            
            while(idx < msg.length()) {
                if(!map.containsKey(str + msg.charAt(idx))) {
                    break;
                }
                else {
                    str += msg.charAt(idx);
                }
                
                idx++;
            }
            
            // [단계3] w에 해당하는 사전의 색인 번호 출력
            list.add(map.get(str));
            
            // [단계4] 입력에서 처리되지 않은 다음 글자가 남아있다면, w + c를 사전에 등록
            if(idx < msg.length()) {    // w + c
                map.put(str + msg.charAt(idx), map.size() + 1);
            }
        }
        
        int[] answer = new int[list.size()];
        for(int i = 0 ; i < answer.length ; i++)
            answer[i] = list.get(i);
        return answer;
    }
}

 

 

 

➕ 다른 풀이 방식

재귀 사용한 풀이

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

class Solution {
    static HashMap<String, Integer> map = new HashMap<String, Integer>();
    static ArrayList<Integer> list = new ArrayList<Integer>();
    static char[] arr;
    static int num = 1;
    
    public int[] solution(String msg) {

    for(int i = 0;i < 27;i++) map.put(String.valueOf((char)(65+i)), i+1);
    arr = msg.toCharArray();

    while(num <= arr.length) {
        String tmp;
        if(num == arr.length) tmp = "" + arr[num-1];
        else tmp = "" + arr[num - 1] + arr[num];

        encoding(tmp);          
    }
    
    int[] answer = new int[list.size()];
    int size = 0;
    for(int i : list) {
        answer[size++] = i;
    }

    return answer;
  }
  
    static void encoding(String tmp) {
        int ans = 0;
        num++;
        if(map.containsKey(tmp) && num < arr.length) {
            encoding(tmp + arr[num]);           
        }
        else if(map.containsKey(tmp)){
            num += 2;
            list.add(map.get(tmp));
        }
        else {
            map.put(tmp, map.size());
            tmp = tmp.substring(0, tmp.length()-1);

            list.add(map.get(tmp));
        }
    }
}

 

 

---

💦 어려웠던 점

- while문 제대로 생각 안 하고 작성한 거

- 안쪽에서도 while문 쓸 생각을 못 했던 것

- 다음 문자 c 저장 방법

- 헷갈렸던 포인트를 말로 설명하기가 쉽지 않다..ㅠ

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[코딩테스트] 프로그래머스 - [3차] 압축(Java)