[Programmers] Lv2. 순위 검색 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

정말 정말 정말 정말 정말 짜증났던 문제입니다. C++은 왜 Python처럼 문자열 라이브러리가 강력하지 않은 걸까요...

문제를 보자마자 생각났던 건 데이터베이스 수업 시간 때 배웠던 B+ 트리였지만, 코딩 테스트 칠 때 언제 그걸 다 구현하겠습니까... 노가다적인(브루트 포스) 방법 말고 다른 방법이 없나 고민하다가 없어서 다른 사람들 풀이를 약간만 봤는데, 거의 다 브루트 포스로 쿼리를 추가해 놓는 방법을 쓰셨더라구요.

 

 

가령 예를 들어, "java backend junior pizza 150"의 데이터(info)가 들어왔다고 가정합니다. 150은 코딩 테스트 점수라 별도로 보기에, 여기에서 봐야 할 카테고리 종류는 총 4가지입니다. 하지만 각 카테고리에 "-"도 쿼리에 들어갈 수 있으므로, 해당 데이터에서 파생될 수 있는 쿼리의 종류는 총 16가지입니다.

"java", "backend", "junior", "pizza"
"java", "backend", "junior", "-"
"java", "backend", "-", "pizza"
"java", "backend", "-", "-"
...

 

 

즉, 핵심은 하나의 데이터가 들어왔을 때, 해당 데이터로부터 파생될 수 있는 모든 쿼리문들을 저장해 놓는 것입니다.

그 후, 실제 쿼리에서 해당 쿼리문을 키(key) 값으로 하여 원하는 value를 찾는 전략이지요.

 

하지만 value(즉, 코딩테스트 점수들)에는 중복된 값도 있을 것이고, 일정 기준 점수 이상인 사람들 수를 구하려면 오름차순으로 정렬된 상태에서 이진 탐색(Binary search)를 하는 것이 유리하다고 생각했습니다.

 

그래서 저는 multiset을 사용하였는데, 효율성 테스트에서 시간 초과가 떴습니다... 아무래도 트리 구조 변경에 많은 시간이 소요되나 봅니다. 그래서 multiset에서 vector로 바꾸고, 오름차순 정렬 후에 쿼리 처리를 진행하였습니다.

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <algorithm>
using namespace std;
const int MAX_CATEGORIES = 4;

vector<string> Split(string str, const string delimiter) {
    int removeNums = delimiter.length();
    int startIdx = 0;
    vector<string> result;

    while (true) {
        int findIdx = str.find(delimiter, startIdx);

        if (findIdx == str.npos)
            break;

        string token = str.substr(startIdx, findIdx - startIdx);
        result.emplace_back(token);
        startIdx = findIdx + removeNums;
    }

    string remainedStr = str.substr(startIdx);
    istringstream tokenizer(remainedStr);
    string buffer;

    while (getline(tokenizer, buffer, ' ')) result.emplace_back(buffer);
    return result;
}

void RegistKey(map<string, vector<int>>& database, const vector<string>& tokens, string buffer, int idx) {
	if (idx == MAX_CATEGORIES) {
		database[buffer].emplace_back(stoi(tokens.back()));
		return;
	}

	RegistKey(database, tokens, buffer + tokens[idx], idx + 1);
	RegistKey(database, tokens, buffer + "-", idx + 1);
}

vector<int> solution(vector<string> info, vector<string> query) {
    map<string, vector<int>> database;
    vector<int> answer;

    // 1. 16가지 경우의 모든 가능한 쿼리 데이터 저장하기
    for (const auto& data : info) {
        istringstream tokenizer(data);
        vector<string> tokens(MAX_CATEGORIES + 1);

        tokenizer >> tokens[0] >> tokens[1] >> tokens[2] >> tokens[3] >> tokens[4];
        RegistKey(database, tokens, "", 0);
    }

    // 2. 쿼리 내 데이터들 오름차순 정렬
    for (auto& info : database)
        sort(info.second.begin(), info.second.end());

    //// 3. 쿼리에 대한 답 추가하기
    for (const auto& request : query) {
        vector<string> splitStr = Split(request, " and ");
        int codingTestScore = stoi(splitStr.back());

        string key;
        for (int i = 0; i < splitStr.size() - 1; i++)
            key += splitStr[i];

        auto findIt = lower_bound(database[key].begin(), database[key].end(), codingTestScore);
        answer.emplace_back(database[key].size() - (findIt - database[key].begin()));
    }

    return answer;
}