[프로그래머스] 순위 검색 (2021 KAKAO Blind Recruitment)

문제 링크

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

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

 

풀이

1) 쿼리를 바로 풀 수 있도록 각 info를 전처리해줍니다.

map을 사용해 "-"를 포함한 모든 조합을 key로 하고, 그 조합에 해당하는 점수들을 vector로 관리해주면 됩니다.

 

"java backend junior pizza 150"로 예를 들어봅시다.

이 하나의 info에서 "-"를 포함시켜 다음과 같은 16가지의 조합을 미리 구할 수 있습니다.

{ java, backend, junior, pizza }

{ -, backend, junior, pizza }

{ java, -, junior, pizza }

{ java, backend, -, pizza}

...

{ -, -, junior, pizza }

{ -, backend, -, pizza }

...

{ -, -, -, - }

 

이렇게 구한 각 조합을 key로 하는 vector에 입력으로 들어온 점수를 추가해줍니다. (line 17 ~ 18)

 

모든 info에 대해 위의 과정을 거치면 모든 조합에 해당되는 점수들의 리스트를 얻을 수 있습니다.

 

2) 각 리스트를 정렬해줍니다. (line 21 ~ 23)

3) 점수들이 오름차순으로 정렬되었으므로, lower bound를 이용해 찾고자 하는 점수의 위치를 빠르게 구할 수 있습니다.

 

정답 코드

#include <bits/stdc++.h>
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
#define FOR(i) for(int i=0; i<2; i++)
using namespace std;
using vs = vector<string>;


vector<int> solution(vector<string> info, vector<string> query) {
	map<tuple<string, string, string, string>, vector<int>> m;
	for(const string &s: info){
  		char a[22], b[22], c[22], d[22];
		int score;
		sscanf(s.c_str(), "%s %s %s %s %d", a, b, c, d, &score);
		
		string aa[2] = {string(a), "-"}, bb[2] = {string(b), "-"}, cc[2] = {string(c), "-"}, dd[2] = {string(d), "-"};
		FOR(i)FOR(j)FOR(k)FOR(w) m[{aa[i], bb[j], cc[k], dd[w]}].push_back(score);
	}
	
	for(auto &now: m){
		sort(all(now.sd));
	}
	
	vector<int> ans;
	for(const string &q: query){
		char a[22], b[22], c[22], d[22];
		int score;
		sscanf(q.c_str(), "%s and %s and %s and %s %d", a, b, c, d, &score);
		
		vector<int> x = m[{string(a), string(b), string(c), string(d)}];
		ans.push_back(x.end() - lower_bound(all(x), score));
	}
	
	return ans;
}