[2018 KAKAO BLIND RECRUITMENT] [3차] 압축

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

코딩테스트 연습 - [3차] 압축 | 프로그래머스

 

 

 

아무리 봐도 카카오는 문자열 문제를 정말 좋아한다...

 

 

 

---

 

 

이번 문제는, 설명이라기보다는 코드를 보면 쉽게 이해할 수 있다. 문자열 문제가 그렇듯, 항상 인덱스의 범위를 확인해줘야 한다. 이번 코드를 풀기 위해서 2중 while문을 작성했는데, 종료되지 않은 경우가 있었다.

 

 

 

       // Find

        while (m.count(msg.substr(idx, len)) != 0) {

            cout << msg.substr(idx, len) << endl;

            pnt = m[msg.substr(idx, len)];

            if (idx + len - 1 > msg.size() - 1)

                break;

            len += 1;

        }

 

 

 

위의 부분인데, if문을 넣지 않으면 코드가 계속 돈다. 마지막 문자가 하나 검사될 경우에, 한 개의 문자열은 처음부터 압축 자료구조에 들어있으므로 절대로 종료되지 않는다.

 

 

 

 

이 부분은, 압축 자료구조에 해당 문자열이 있어도 종료되므로, 아래 코드에서 압축 문자열에 들어있는지 확인하는 코드를 작성하였다. 

 

 

 

 

        // Insert

        if (len != 1)

            m[msg.substr(idx, len)] = m.size() + 1;

 

 

 

처음에는 위처럼 작성했는데, 신기하게 통과되었다. 하지만, 추후에 문제를 알게 되었는데, 이렇게 작성할 경우에 압축 자료구조를 갱신할 수도 있다. 따라서, 압축 자료 구조가 들어있는지 확인하는 조건문으로 변경을 해야 한다. 해설 코드에서는 올바르게 작성하였다.

 

 

 

---

 

 

해설코드(C++).

 

#include <string>

#include <vector>

#include <iostream>

#include <map>

 

using namespace std;

 

vector<int> solution(string msg) {

    vector<int> answer;

    map<string, int> m;

    for (char c = 'A'; c <= 'Z'; c++) {

        char str[2];

        str[0] = c;

        str[1] = '\0';

        m[str] = c - 'A' + 1;

    }

 

 

    int idx = 0;

    while (idx < msg.size()) {

        int len = 1;

        int pnt = 0;

 

        // Find

        while (m.count(msg.substr(idx, len)) != 0) {

            cout << msg.substr(idx, len) << endl;

            pnt = m[msg.substr(idx, len)];

            if (idx + len - 1 > msg.size() - 1)

                break;

            len += 1;

        }

 

        // Insert

        if (m.count(msg.substr(idx, len)) != 0)

            m[msg.substr(idx, len)] = m.size() + 1;

        

        // Answer

        answer.push_back(pnt);

        cout << pnt << endl;

 

 

        idx += len - 1;

    }

    return answer;

}