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

순위 검색

일하다보니… 공부가 소홀해진걸 깨닫고… 알고리즘 문제를 다시 풀고 있습니다…

이 문제는 2021 카카오 블라인드 공채 코테 문제입니다.

문제를 보면 일단 거대한 문자열들이 보입니다. 이걸 전처리부터 하는게 중요하겠죠? 전 C++로 풀었기 때문에 stringstream을 사용하였지만 파이썬이나 자바라면 split으로 한번에 해결될겁니다.

문자를 분리한 후 해당하는 조건에 맞는 값들을 맵을 이용해서 저장해놔야 합니다.

그러기위해선 간단한 dfs함수를 구현하였고 “-“ 이 부분이 입력되면 그에따른 값도 추가해야해서 두개를 구현하였습니다.

그리고 해당하는 지원자가 몇명인지를 확인하는 부분에선 lower_bound를 사용했습니다. 그 이유는 입력받은 score보다 큰 사람이 몇명인지 세기엔 lower_bound 나 upper_bound를 사용하는게 효율적이라 생각했기 때문입니다.

풀이는 다음과 같습니다.

Source Code:

#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;

#define ALL "-"
unordered_map<string, vector<int>> applicant;

string appl[4][2];

void analysis(int score, string target, int cnt, int idx) {
	if (cnt == 4) {
		applicant[target].push_back(score);
		return;
	}

	for (int i = idx; i<4; i++) {
		analysis(score, target + appl[i][0], cnt + 1, i + 1);
		analysis(score, target + appl[i][1], cnt + 1, i + 1);
	}
}


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

	appl[0][1] = ALL;
	appl[1][1] = ALL;
	appl[2][1] = ALL;
	appl[3][1] = ALL;



	for (string& i : info) {
		istringstream iss(i);
		iss >> appl[0][0] >> appl[1][0] >> appl[2][0] >> appl[3][0] >> score;

		analysis(score, "", 0, 0);
	}

    for(auto& ap : applicant) sort(ap.second.begin(),ap.second.end());
    
    for(string& q : query){
        istringstream iss(q);
        string key[4],tmp;
        iss >> key[0] >> tmp >> key[1] >> tmp >> key[2] >> tmp >> key[3] >> score;
        
        string pass_check = key[0] + key[1] + key[2] + key[3];
        
        vector<int> apply_score = applicant[pass_check];
        
        answer.push_back(apply_score.end() - lower_bound(apply_score.begin(),apply_score.end(),score));
    }

	return answer;
}

궁금하신 점은 댓글 남겨 주세요!!

Summary

• 조심으로 돌아가고 있습니다.