22.04.08. 풀었던 문제들

1. [1차] 프렌즈4블록

쫄았는데 생각보다 풀 만 하다. 시간도 꽤 빨리 풀었고... 단순 구현 문제였다.

​

​

2. [3차] 압축

문자열과 map을 사용하는 문제다. 주어지는 대로 구현하면 되고, index가 잘 계산되었는지만 신경쓰면 된다.

// 압축

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

vector<int> solution(string msg) {
    // 단계 1
    map<string, int> dict;
    vector<string> alphabet = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};
    int dict_idx = 1;
    for(dict_idx = 1; dict_idx < 27; dict_idx++)
        dict[alphabet[dict_idx-1]] = dict_idx;
    
    vector<int> answer;
    int maxlen = 1, msg_length = msg.length();
    for(int i = 0; i<msg_length;){
        if(i + maxlen >= msg_length) maxlen = msg_length - i;
        // 단계 2
        for(int len = maxlen; len >= 1; len--){
            string substring = msg.substr(i, len); // 가장 긴 문자열 
            
            // 단계 3
            if(dict[substring] != 0){
                answer.push_back(dict[substring]);
                
                // 단계 4
                if(i + len < msg_length){
                    maxlen = max(maxlen, len + 1);
                    dict[msg.substr(i, len + 1)] = dict_idx++;
                }
                
                i += len;
                break;
            }
        }
    }
    
    
    return answer;
}