프로그래머스 - [3차]압축 (C++, Java)

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

프로그래머스

 

 

문자열 구현 문제이다. 

지문을 이해하는 것이 가장 핵심이고 주어진 알고리즘을 그대로 구현할 수 있는지 물어보고 있다.

이런 종류의 문제는 난이도 있는 코딩테스트의 1번으로 주어질만하다. 그리고 설명을 그대로 따라하지 않으면 분명 예외 케이스가 있기 때문에 본인의 자아를 빼고 있는 그대로 구현하는 것이 핵심이다.

 

개인적으로 항상 이런 디테일을 요하는 문제에서 한번에 AC를 받지 못하는 섬세함이 부족한 편인데 이번엔 의외로(?) 한번에 AC를 받아서 기분이 좋다.

 

C++ 코드

#include <string>
#include <vector>
#include <map>
using namespace std;

map<string, int> dic;

string subSTR(string s, int n){
    string r = "";
    
    for(int i = n; i < s.size(); i++){
        r += s[i];
    }
    
    return r;
}

vector<int> solution(string msg) {
    vector<int> answer;
    
    for(char i = 'A'; i <= 'Z'; i++){
        string tmp = "";
        tmp.push_back(i);
        dic.insert({tmp, i - 'A' + 1});
    }
    
    int idx = 0;
    while(msg.size() > 0){
        string w = "";
        string wc = "";
        int i;
        for(i = 0; i < msg.size(); i++){
            w += msg[i];
            
            if(dic.find(w) == dic.end()){ // 못찾음
                wc = w;
                w.pop_back();                
                break;
            }
        }
        dic.insert({wc, dic.size() + 1});
        answer.push_back(dic[w]);
        msg = subSTR(msg, i);
    }
    
    return answer;
}

 

Java 코드

import java.util.*;

class Solution {
    static HashMap<String, Integer> dict = new HashMap<>();
    
    public ArrayList<Integer> solution(String msg) {
        ArrayList<Integer> answer = new ArrayList<>();
        
        for(char word = 'A'; word <= 'Z'; word++){
            String tmp = "";
            tmp += word;
            
            dict.put(tmp, word - 'A' + 1);
        }
        
        while(msg.length() > 0){
            String w = "";
            String wc = "";
            int i = 0;
            for(; i < msg.length(); i++){
                w += msg.charAt(i);
                
                if(!dict.containsKey(w)){
                    wc = new String(w);
                    w = w.substring(0, w.length() - 1);
                    
                    break;
                }
            }
            
            answer.add(dict.get(w));
            dict.put(wc, dict.size() + 1);
            
            msg = msg.substring(i, msg.length());
        }
        
        return answer;
    }
}