코테/프로그래머스

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

imname1am 2024. 2. 23. 23:57
반응형

📖 문제

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

💡  풀이 방식

• 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로 돌아간다.

 

 

 

[ 진행 과정 ] 

 

 

 

🔺 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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;
    }
}
cs

 

 

 

➕ 다른 풀이 방식

재귀 사용한 풀이

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)

레벨: 2언어: 자바(Java)해당 문제는 알고리즘 문제라기보단 적절한 자료구조를 이용하면 풀수 있는문제입니다..간단하지는 않으니 레벨2로 분류된듯 싶습니다.저의 풀이방법을 대해 설명드리면1

velog.io

 

반응형