문제
info에 지원자 정보가 주어진다. 각 문자열은 "언어, 직군, 경력, 소울푸드, 점수"를 나타낸다. query는 조건을 나타내는데 예를 들어 "java and backend and junior and pizza 100"는 "코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 지원자는 몇 명인가?"를 의미한다. 조건의 각 속성은 "-"라고 표시될 수 있는데 "-"는 해당 조건을 고려하지 않겠다는 뜻이다. 각 query 조건을 만족하는 지원자의 수를 구한다. 입력 예시는 다음과 같다.
// info
["java backend junior pizza 150",
"python frontend senior chicken 210",
. . .]
// query
["java and backend and junior and pizza 100",
"- and backend and senior and - 150",
"- and - and - and - 150"]문제 풀이
1
info의 문자열의 파싱하여 모든 경우를 unordered_map에 담는다. (<string, vector<int>> 각 경우를 key값으로, 점수를 value로 unordered_map에 저장)
예를 들어 "java backend junior pizza 150"는 "jbjp"와 점수 150로 정리할 수 있는데, jbjp가 조건을 만족하는 쿼리는 jbjp / j--- / jbj- / ---- 등 총 16가지 경우가 가능하다.
unordered_map["j---"]에는 "j---"를 만족하는 점수 벡터가 담긴다.
2
unordered_map 각 key에 해당하는 점수들을 오름차순으로 정렬한다.
for(auto iter = um.begin(); iter !=um.end();iter++){
sort(iter->second.begin(), iter->second.end());
}3
query를 돌면서 각 쿼리를 "----" 형태로 파싱하고, unordered_map에서 쿼리에 해당하는 점수들을 구한다.
vector<int> scores = um[s];4
점수들은 오름차순으로 정렬되어 있으므로 점수보다 크거나 같은 점수의 인덱스를 구한다.
예를 들어 scores = {50, 70, 100, 100, 200}이고 조건인 score가 100이라면
int idx = lower_bound(scores.begin(), scores.end(), score) - scores.begin();의 결과 idx는 2가 된다. lower_bound는 기준인 score 보다 크거나 같은 값의 주소를 리턴한다. (upper_bound는 초과하는 값의 주소!)
그렇다면 100 이상이 되는 점수의 개수는 scores.size()-idx가 된다.
unordered_map
- unordered_map의 탐색 시간복잡도는 O(1)이다. (hash 테이블)
- map의 탐색 시간 복잡도는 O(log n)이다. (이진 탐색 트리)
- 데이터가 많을 때 map에 비해 월등한 성능을 보이지만 key가 유사한 데이터가 많으면 해시 충돌로 성능이 저하될 수 있다.
- 탐색 시 인덱스로 접근할 수 없고, iterator로 접근한다.
- key는
iter->first, value는iter->second
lower_bound, upper_bound
- 이진탐색으로 원소를 탐색한다. (즉 정렬이 되어있어야 한다.)
- lower_bound는 키값 이상이 되는 수의 주소
- upper_bound는 키값 초과하는 수의 주소
소스코드
#include <string>
#include <vector>
#include <sstream>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map<string, vector<int>> um;
void allCase(string str, int score){
char arr[4][2] = {{str[0],'-'},{str[1],'-'},{str[2],'-'},{str[3],'-'}};
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++){
string tmp = "";
tmp += arr[0][i]; tmp += arr[1][j]; tmp += arr[2][k]; tmp += arr[3][l];
um[tmp].push_back(score);
}
}
}
}
}
vector<int> solution(vector<string> info, vector<string> query) {
vector<int> answer;
for(auto i: info){
string str[4];
int score;
stringstream ss(i);
ss>>str[0]>>str[1]>>str[2]>>str[3]>>score;
string s = "";
s +=str[0][0]; s +=str[1][0]; s +=str[2][0]; s +=str[3][0];
allCase(s, score);
}
for(auto iter = um.begin(); iter !=um.end();iter++){
sort(iter->second.begin(), iter->second.end());
}
for(auto i: query){
string str[4], aand;
int score;
stringstream ss(i);
ss>>str[0]>>aand>>str[1]>>aand>>str[2]>>aand>>str[3]>>score;
string s = "";
s +=str[0][0]; s +=str[1][0]; s +=str[2][0]; s +=str[3][0];
vector<int> scores = um[s];
//sort(scores.begin(), scores.end());
if(scores.size()!=0){
int idx = lower_bound(scores.begin(), scores.end(), score) - scores.begin();
answer.push_back(scores.size()-idx);
}else answer.push_back(0);
}
return answer;
}lv2인데 너무 어렵다...🥲
for(auto iter = um.begin(); iter !=um.end();iter++){
sort(iter->second.begin(), iter->second.end());
}를 빼고, vector<int> scores = um[s];를 구한 다음에 sort하고 lower_bound를 구하면 효율성 테스트를 통과하지 못한다. ¯\(°_o)/¯ ?
