2018 KAKAO BLIND RECRUITMENT > [3차] 압축

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/17684

프로그래머스

 

구현 문제라 생각하였다. 읽어본 결과 아래와 같이 풀 수 있다 생각하였다.

 

//순차적으로 탐색 +1 씩

//현재 위치에서 탐색할 수 있는 문자열 중 사전에 있는 것 중 가장 긴 것 번호 출력

//(가장 긴 것 + 그 다음 문자)가 없다면 사전에 추가 //따라서 각 위치에서 사전에 없다는 소리 나올 떄까지 부분 문자열 길이 늘려보기 하면 됨.

//그런 다음에 더 안 늘어나면 번호 출력

//남은게 있다면 뒤에꺼 더해서 사전에 추가

 

아래는 이를 구현한 코드이다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

    // 1. 초기화: A=1, B=2, ..., Z=26
    for (char ch = 'A'; ch <= 'Z'; ch++) {
        string str(1, ch);
        list[str] = ch - 'A' + 1;
    }

    // 2. 메시지 탐색 및 압축
    int idx = 27; // 다음 사전에 추가될 인덱스 번호
    for (int i = 0; i < msg.size(); ) {
        string tmp = string(1, msg[i]);
        int num = list[tmp];

        // 사전에 없을 때까지 문자열 길이를 늘려가며 탐색
        while (list.find(tmp) != list.end() && i < msg.size() - 1) {
            num = list[tmp]; // 현재 문자열의 사전 번호 저장
            i++;
            tmp += msg[i];   // 다음 문자를 추가
        }

        // 현재 사전 번호를 출력
        answer.push_back(num);

        // 새로운 문자열을 사전에 추가
        if (list.find(tmp) == list.end()) {
            list[tmp] = idx++;
        }
    }

    return answer;
}

 

실행해본 결과 시간 초과가 났다.

아마 문자열을 직접 탐색한 것이 원인이라 추측되어 이를 슬라이싱으로 변경하였다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

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

    // 1. 초기화: A=1, B=2, ..., Z=26
    for (char ch = 'A'; ch <= 'Z'; ch++) {
        string str(1, ch);
        list[str] = ch - 'A' + 1;
    }

    // 2. 메시지 탐색 및 압축
    int idx = 27; // 다음 사전에 추가될 인덱스 번호
    for (int i = 0; i < msg.size(); ) {
        int length = 1;
        int num = 0;

        // 문자열 슬라이싱으로 탐색 (복사 대신 참조)
        while (i + length <= msg.size() && list.find(msg.substr(i, length)) != list.end()) {
            num = list[msg.substr(i, length)]; // 현재 사전 번호
            length++;
        }

        // 현재 사전 번호를 출력
        answer.push_back(num);

        // 새로운 문자열을 사전에 추가
        if (i + length <= msg.size()) {
            list[msg.substr(i, length)] = idx++;
        }

        // 다음 위치로 이동
        i += length - 1;
    }

    return answer;
}

 

그랬더니 성공하였다.