[C++] 프로그래머스 - 순위 검색

programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

<풀이>

1. 지원서 정보와 해당 쿼리를 입력받는다.

2. 해당 쿼리에 맞는 지원자의 수를 벡터에 담아 반환한다.

 

<해법>

1. "효율성 테스트"가 있는 문제의 마음가짐

=> 이 문제는 효율성 테스트가 있는 문제입니다. 따라서, 쿼리 하나씩 모든 지원서 정보를 찾으면서 풀이를 할 경우 시간복잡도가 50,000 x 100,000 이므로 문제를 통과할 수 없습니다. 그렇다면 이 때 '지원서 정보를 잘 정리해야겠다.' 라는 생각을 해야합니다. 더 나아가서, 어떤 자료구조와 알고리즘을 사용해야 할 지 생각해야합니다. "효율성 테스트"가 있는 문제는 단순히 구현을 묻는 문제가 아닙니다. 문제에 맞는 자료구조와 알고리즘을 떠올릴 수 있는지가 문제의 핵심입니다.

 

2. 지원서 정보를 정리하는 방법

=> '지원서 정보를 잘 정리해야겠다.' 는 생각까지 하였습니다. 하지만, 물음에 쉽게 답이 나오지 않습니다. 마땅한 정렬방법이 없기 때문입니다. 이 때, 생각을 전환하여 '쿼리에 맞는 지원서를 정리할 수 있을까?'라는 생각을 할 수 있어야합니다. 해당 지원서 정보가 가능한 모든 쿼리들에 저장해놓는 방식입니다. 

위와 같이 정리를 해놓고, 해당 쿼리마다 만족되는 점수들의 개수를 구합니다. 만족되는 점수들의 개수를 구할 때, 점수들을 정렬해놓고 이분탐색을 이용하면 더 빠르게 찾을 수 있습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
 
using namespace std;
 
map<string, vector<int>> m;
 
void infoIntoMap(string info) {
 
    string infoArr[4][2] = {
        {"-"},
        {"-"},
        {"-"},
        {"-"}
    };
    int infoScore = 0;
 
    //info 띄어쓰기 분리
    istringstream iss(info);
    iss >> infoArr[0][1] >> infoArr[1][1] >> infoArr[2][1] >> infoArr[3][1] >> infoScore;
 
    //info가 해당될 수 있는 모든 쿼리 만들기
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 2; l++) {
                    //map의 key
                    string infoString = infoArr[0][i] + infoArr[1][j] 
                                          + infoArr[2][k] + infoArr[3][l];     
                    
                    //map에 저장
                    m[infoString].push_back(infoScore);
                }
            }
        }
    }
}
 
int findQueryFromMap(string query) {
 
    int output = 0;
 
    string queryArr[4];
    int queryScore = 0;
 
    //query 띄어쓰기 분리
    string trash = "";
    istringstream iss(query);
    iss >> queryArr[0] >> trash >> queryArr[1] >> trash 
        >> queryArr[2] >> trash >> queryArr[3] >> queryScore;
 
    //map의 key만들기
    string queryString = "";
    for (int i = 0; i < 4; i++) {
        queryString += queryArr[i];
    }
 
    //findScores = map의 value
    vector<int> findScores = m[queryString];
 
    //해당 백터에서 queryScore의 lower_bound를 찾고 개수 계산
    output = findScores.end() - lower_bound(findScores.begin(), findScores.end(), queryScore);
 
    //개수 반환
    return output;
}
 
vector<int> solution(vector<string> info, vector<string> query) {
 
    vector<int> answer;
 
    //주어진 info를 map에 담기
    for (int i = 0; i < info.size(); i++) {
        infoIntoMap(info[i]);
    }
 
    //map에 저장되어 있는 점수들 정렬
    for (auto& instance : m) {
        sort(instance.second.begin(), instance.second.end());
    }
 
    //query를 분리해서 answer에 저장
    for (int i = 0; i < query.size(); i++) {
        answer.push_back(findQueryFromMap(query[i]));
    }
 
    //반환
    return answer;
}

 

문제 해결 능력에 대해 알아볼 수 있는 문제였습니다.