[Programmers]#Level2_압축, map, string

#1. 문제

프로그래머스

 

 

---

 

#2. 풀이

 

1. map

[Basic C++] #38_map, 연관 컨테이너

map 컨테이너는 C++ 표준라이브러리에서 제공하는 연관 컨테이너로, 키와 값을한 쌍으로 군형 이진 트리에 저장합니다. 특히, map 컨테이너는 키의 중복을 허용하지 않고, 내부적으로 항상 정렬된 상태를 유지합니다. map 컨테이너의 접근/삽입/삭제 작업의 시간 복잡도는 최악의 경우 O(log n)입니다.

 

2. map을 통해 현재 문자열이 사전에 등록되어 있는지 체크

1. 먼저, 알파벳 순서대로 각 문자를 키로 그 순서를 값으로 map 컨테이너를 초기화합니다.
2. 다음으로, msg 문자열의 0번 인덱스부터 차례대로 문자열을 구성해 나갑니다. 현재 문자열이 map(사전)에 이미 등록되어 있는지 확인합니다.
3. 만약, 현재 문자열이 사전에 없다면, 마지막 문자를 제외한 나머지 문자열에 대하여 색인 번호를 구하고, 이들을 한 쌍으로 사전에 등록해 줍니다.
4. 만약, 현재 문자열이 사전에 있다면, 다음 문자로 넘어갑니다.
5. 마지막으로, 모든 작업을 끝내고 남은 문자열의 색인 번호를 정답 목록에 삽입해 주고, 마칩니다.

 

---

 

#3. 코드

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

using namespace std;

#define START 27

int cPos = 27;
map<string, int> m;

vector<int> solution(string msg) {
    vector<int> answer;

    // 초기 사전 구성
    for (char c = 'A'; c <= 'Z'; ++c) {
        string s(1, c);
        m[s] = c - 'A' + 1;
    }

    int idx = 0;
    string str = "";

    while (idx < msg.length()) {
        str += msg[idx];
        
        // 사전에 없다면?
        if (m.find(str) == end(m)) {
            // 현재 문자열에서 마지막 문자 제거
            string prev = str.substr(0, str.length() - 1);
            // 정답 목록에 현재 문자열에 대한 색인 번호 추가
            answer.push_back(m[prev]);
            // 현재 문자열을 사전에 추가
            m[str] = cPos++;
            // str을 마지막 문자로 초기화
            str = str.back();
        }
        idx++;
    }

    // 마지막 남은 문자열의 색인 번호 추가
    if (!str.empty()) {
        answer.push_back(m[str]);
    }

    return answer;
}

 

---