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

문제 링크 :

• https://programmers.co.kr/learn/courses/30/lessons/72412

문제 요약 :

• 스트링으로 주어지는 요구사항을 만족하는 이용자를 찾아내는 쿼리 구현하기

풀이 흐름 :

• 분명 SQL 쿼리를 써서 찾아내야 할 것만 같은데.. 그걸 C++로 구현을 하라고? 싶었음

• 탐색에 용이해야 하니까 map을 쓸까 하다가, 찾아야 할 조건이 4개인데 어느걸 key로 두고 어느걸 value로 둘지 고민하다가 각이 안나와서 관둠. 그렇다고 4차원 배열을 쓰라고?? 설마?? 싶어서 다른 방법 고민.

• 결국 시간을 잡아먹고 구글링

• https://yjyoon-dev.github.io/kakao/2021/01/29/kakao-ranksearch/
  해당 페이지의 풀이 방법 참고하여 풀었다.
  기준이 되는 4가지를 분류하기 위해 4차원 배열을 쓰고(진짜라니) 특정 분류를 충족하는 사람이 여러명일 수 있으니 vector로 점수를 관리한다.
  탐색 효율을 위해 반복 범위를 좁혀야 함. 쿼리 중 '모든조건'을 뜻하는 '-' 는 반복문 범위를 전체로 하고, 다른 녀석들은 반복문 범위를 하나로 한정하여 4중for문 돌려버림.
  그리고 조건을 만족하는 사람들 중 최소 점수를 가진 사람의 인덱스를 알아내고, '조건 만족하는 사람 총 인원 수 - 인덱스' 해서 사람 수 구함.

---

코드

사용 언어 : C++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> answer;
vector<int> applicant[4][3][3][3];

void splitInfo(vector<string>infoList){
	for (string info : infoList){
		// "java backend junior pizza 150"
		string tmp = "";
		vector<int> split;

		for (int i = 0; i < info.length(); i++){
			char c = info[i];
			if (c == ' '){
				// 잘라
				if (tmp == "cpp" || tmp == "backend" || tmp == "junior" || tmp == "chicken")
					split.push_back(0);
				else if (tmp == "python")
					split.push_back(2);
				else
					split.push_back(1);
				tmp = "";
			}
			else{
				tmp += c;
			}
		}
		split.push_back(stoi(tmp));	// 점수

		applicant[split[0]][split[1]][split[2]][split[3]].push_back(split[4]);
	}
	return;
}

void searchByQuery(vector<string> q){
	int begin_i = 0, end_i = 0;
	int begin_j = 0, end_j = 0;
	int begin_k = 0, end_k = 0;
	int begin_l = 0, end_l = 0;

	// "언어" and "직군" and "경력" and "푸드" and "점수"
	if (q[0] == "cpp"){ begin_i = end_i = 0; }
	else if (q[0] == "java"){ begin_i = end_i = 1; }
	else if (q[0] == "python") { begin_i = end_i = 2; }
	else{ begin_i = 0;  end_i = 2; }

	if (q[2] == "backend") { begin_j = end_j = 0; }
	else if (q[2] == "frontend") { begin_j = end_j = 1; }
	else { begin_j = 0;  end_j = 1; }

	if (q[4] == "junior") { begin_k = end_k = 0; }
	else if (q[4] == "senior") { begin_k = end_k = 1; }
	else { begin_k = 0;  end_k = 1; }

	if (q[6] == "chicken") { begin_l = end_l = 0; }
	else if (q[6] == "pizza") { begin_l = end_l = 1; }
	else { begin_l = 0;  end_l = 1; }

	int score = stoi(q[7]);
	int count = 0;

	for (int i = begin_i; i <= end_i; ++i){
		for (int j = begin_j; j <= end_j; ++j){
			for (int k = begin_k; k <= end_k; ++k){
				for (int l = begin_l; l <= end_l; ++l){
					vector<int> thisQuery = applicant[i][j][k][l];
					auto iter = lower_bound(thisQuery.begin(),thisQuery.end(),score);
					if (iter == thisQuery.end()) continue;
					else
						count += thisQuery.size() - (iter - thisQuery.begin());
				}
			}
		}
	}
	answer.push_back(count);
}

void splitQuery(vector<string> query_list){
	for (string query : query_list){
        // "java and backend and junior and pizza 100"
		string tmp;
		vector<string> split;

		for (int i = 0; i < query.length(); i++){
			char c = query[i];
			if (c == ' '){
				split.push_back(tmp);
				tmp = "";
			}
			else{
				tmp += c;
			}
		}
		split.push_back(tmp);
		searchByQuery(split);
	}
}
vector<int> solution(vector<string> info, vector<string> query) {

	splitInfo(info);

	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 2;++j)
			for (int k = 0; k < 2;++k)
				for (int l = 0; l < 2; ++l)
					sort(applicant[i][j][k][l].begin(), applicant[i][j][k][l].end());

	splitQuery(query);

	return answer;
}