[프로그래머스 2021 KAKAO BLIND RECRUITMENT] 순위 검색

문제

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

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

 

풀이

본 풀이는 c++를 기준으로 작성하여 파싱하는 과정이 지저분할 수 있습니다.. 

---

1. info의 정보들을 매핑하는 과정에서 서로 겹치지 않는 값들을 사용하기 위하여 배열의 크기를 크게 만들었습니다. 

 

2. 쿼리에서 구해야하는 정보들이 모두 특정되지않고 '-'와 같이 해당 쿼리의 모든 원소를 포함하는 문자가 들어올 수 있기때문에 info의 정보들을 변환한 후, 각 정보에 대한 조합을 모두 구해서 점수들을 넣어줍니다.

 

3. 쿼리에서 요구하는 조건을 만족하며 주어진 점수이상의 인원을 lower_bound로 구하기 위해 모든 조합을 순회하며 정렬해줍니다.

 

4. 입력받은 쿼리들도 적절히 파싱한 후, 그 정보들을 미리 정해놓은 숫자들로 변환해주고, 그러한 조건을 모두 만족하는 것이므로 모두 더해줍니다.

 

5. 4에서 구한 인덱스에서 score점수 이상인 값들의 개수를 lower_bound를 이용해서 구해준 뒤 정답에 넣어주면 해결할 수 있습니다.

 

풀이

#include <bits/stdc++.h>
using namespace std;

vector<int> comb[55555];

// 입력 받은 정보를 숫자로 변환
int conv(string x) {
	// cpp java, python : 50000 30000 10000
	// backend frontend : 5000 3000 
	// junior senior : 500 300 
	// chicken pizza : 50 30 

	if (x == "-" || x == "and") return 0;
	int mul = 1, ret;
	if (x == "cpp") ret = 5, mul = 1e4;
	else if (x == "java") ret = 3, mul = 1e4;
	else if (x == "python") ret = 1, mul = 1e4;
	else if (x == "backend") ret = 5, mul = 1e3;
	else if (x == "frontend") ret = 3, mul = 1e3;
	else if (x == "junior") ret = 5, mul = 1e2;
	else if (x == "senior") ret = 3, mul = 1e2;
	else if (x == "chichen") ret = 5, mul = 1e1;
	else if (x == "pizza") ret = 3, mul = 1e1;
	return ret * mul;
}

vector<int> solution(vector<string> info, vector<string> query) {
	vector<int> answer;
	for (string S : info) {
		stringstream ss(S);
		string s;
		int iinfo[4], score;
		memset(iinfo, -1, sizeof(iinfo));
        
		// #1. 입력받은 정보들을 겹치지않는 숫자들로 변환
		while (ss >> s) {
			if (iinfo[0] < 0) iinfo[0] = conv(s);
			else if (iinfo[1] < 0) iinfo[1] = conv(s);
			else if (iinfo[2] < 0) iinfo[2] = conv(s);
			else if (iinfo[3] < 0) iinfo[3] = conv(s);
			else score = stoi(s);
		}

		// #2. 각 정보에 대한 조합을 모두 구해서 점수들을 넣어줌
		for (int i = 0; i < 16; i++) {
			int idx = 0;
			for (int j = 0; j < 4; j++)
				if (i & (1 << j)) idx += iinfo[j];
			comb[idx].emplace_back(score);
		}
	}
    
	for (int i = 0; i < 55555; i++) {
		if (comb[i].empty()) continue;
		// #3. 점수 정렬
		sort(comb[i].begin(), comb[i].end());
	}
    
	for (string Q : query) {
		stringstream ss(Q);
		string q;
		int iinfo[4], score, counter = 0;
		memset(iinfo, -1, sizeof(iinfo));
        
		// #4. 쿼리들도 미리 정한 숫자들로 변환
		while (ss >> q) {
			if (counter == 0) iinfo[0] = conv(q);
			else if (counter == 2) iinfo[1] = conv(q);
			else if (counter == 4) iinfo[2] = conv(q);
			else if (counter == 6) iinfo[3] = conv(q);
			else if (counter == 7) score = stoi(q);
			counter++;
		}
		int idx = 0, cnt = 0;
        
		// #5. 해당 조건을 모두 만족하는 인덱스 값이기에 모두 더해줌.
		for (int i = 0; i < 4; i++) idx += iinfo[i];
        
		// #6. 해당 인덱스에서 score점수 이상인 값들의 개수를 lower_bound를 이용해서 구해줌
		cnt = comb[idx].size() - (lower_bound(comb[idx].begin(), comb[idx].end(), score) - comb[idx].begin());
		
        answer.emplace_back(cnt);
	}
	return answer;
}