프로그래머스 - [3차] 압축

프로그래머스 - [3차] 압축 (0.5h + 하나은행 유형 + 체감 난이도 ★★☆☆☆)

 

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

 

프로그래머스

 

 

 

<해결 방법> - <문자열 & HashMap>

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

-> HashMap 사용 <String(단어), Integer>형식.

 

2. 사전에서 현재 입력(msg)과 일치하는 가장 긴 문자열 w를 찾기(★시간 많이 썼음)

-> msg를 char 배열로 만들고, 반복문을 수행하며 단어가 hashmap의 key로 들어있는 경우는 skip해주며 다음 반복문을 돌았다.

 

3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거

정답을 출력할 answer_list를 만들고, 해당 리스트에 값을 추가한다.

그리고 msg에서는 사전에 추가된 문자열을 제거해준다.

 

 

<정답 코드>

import java.util.*;

class Solution {
    public int[] solution(String msg) {

        List<Integer> ans_list = new ArrayList<>();
        
        // 1. 길이가 1인 모든 단어를 포함하도록 사전 초기화
        Map<String, Integer> dict = new HashMap<>();
        for(int i = 0; i <= 25; i++){
            dict.put(String.valueOf((char) ('A' + i)), i + 1);  
        }
        
        while(msg.length()>0){
            
            // 2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
            char[] arr = msg.toCharArray();
            String w = "" + arr[0]; 
            String input_w = "";
            
            boolean flag = true;
            
            if(arr.length > 1){
                for(int i = 1; i <= arr.length; i++){
                    if(dict.get(w) == null) {
                        flag = false;
                        break;
                    }
                    if(i < arr.length) w += arr[i];
                } 
                
                
                if(flag){
                    input_w = w;
                }else{
                    input_w = w.substring(0, w.length() - 1);  // 가장 긴 문자열      
                }
                
            }else{
                input_w = w;
            }
            
            // 3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
            ans_list.add(dict.get(input_w));    // 정답 리스트에 추가
            msg = msg.substring(input_w.length());
            
            // 4. 입력에서 처리되지 않은 다음 글자가 남아있따면, w+c에 해당하는 단어를 사전에 등록.

            dict.put(w, dict.size() + 1);
        }
        
        int[] answer = new int[ans_list.size()];
        for(int i = 0; i < ans_list.size(); i++){
            answer[i] = ans_list.get(i);
        }
        
        return answer;
    }
}

 

 

<프로그래머스 좋아요 1등 코드>

import java.util.ArrayList;

class Solution {
  public int[] solution(String msg) {
    ArrayList<String> dic = new ArrayList<String>();
    ArrayList<Integer> result = new ArrayList<Integer>();

    for(int i = 0 ; i < 26; i++) {
        dic.add(String.valueOf((char)('A'+i)));
    }

    for(int i = 0 ; i < msg.length() ; i++) {
        for(int j = dic.size()-1 ; j >= 0 ; j--) {
            if(msg.substring(i).startsWith(dic.get(j))) {
                i += dic.get(j).length()-1;
                result.add(j+1);
                if(i+1 < msg.length())
                    dic.add(dic.get(j)+msg.charAt(i+1));
                break;
            }
        }
    }

    int[] answer = new int[result.size()];

    for(int i = 0 ; i < result.size() ; i++) 
        answer[i] = result.get(i);

    return answer;  
  }
}

 

 

부족한 점

1. String 을 자르고 붙이는 스킬이 부족한 것 같다.

2. Java에 String을 다루는 메서드를 다시 암기하고, 응용하기.