순위 검색
프로그래머스 순위 검색 풀이
문제설명
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
- 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
- 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
- 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
- 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는 니니즈
는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?
문의사항에는 “-”을 표시도 사용할 수 있다. “-”는 해당 조건은 신경쓰지 않아도 되는 것을 의미한다. 즉, 개발언어항목에 “-”표시가 오면 언어에 상관없이 나머지 조건으로 찾겠다는 의미이다.
제한사항
- 1 ≤ 지원자수 ≤ 50,000
- 1 ≤ 쿼리 ≤ 100,000
모든 지원자를 vector로 관리하고, 이분 탐색으로 쿼리를 찾으면 빠듯하게? 시간안에 동작한다.
$O(5 * 10^4 * 10^5)$
해결과정
구조체를 통해 지원자 전체를 관리한다. 이를 정렬한 뒤, 이분탐색으로 원하는 범위를 찾는다.
다만 “-”가 나올때는 관련해서 찾아야하는 경우의 수를 모두 구하여 더하는 방식을 선택했다.
예를 들어 모든 조건이 “-”이고, 점수가 100점이상을 찾으면 {cpp, backend, junior, chicken} 부터 {python, frontend, senior, pizza}까지 총 24가지 경우의 수를 모두 구한뒤 값을 더했다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
struct apply{
int lang; //0:cpp, 1:java, 2:python
int type; //0:backend, 1:frontend
int career; //0:주니어, 1:시니어
int food; //0:chickend, 1: pizza
int score; // 코딩테스트 점수
};
unordered_map<string, int> mmap;
void Init(){
mmap["cpp"] = mmap["backend"] = mmap["junior"] = mmap["chicken"] = 0;
mmap["java"] = mmap["frontend"] = mmap["senior"] = mmap["pizza"] = 1;
mmap["python"] = 2;
}
bool compare(const struct apply& a, const struct apply& b){
if(a.lang != b.lang) return a.lang < b.lang;
if(a.type != b.type) return a.type < b.type;
if(a.career != b.career) return a.career < b.career;
if(a.food != b.food) return a.food < b.food;
return a.score < b.score;
}
vector<string> stringsplit(const string& in){
istringstream iss(in);
string token;
vector<string> tokens;
while(iss >> token){
tokens.push_back(token);
}
return tokens;
}
vector<struct apply> db;
bool check(const struct apply& c, const struct apply& test){
if(c.score > test.score || c.lang != test.lang || c.type != test.type || c.career != test.career || c.food != test.food) return false;
return true;
}
int cal(struct apply& input){
int left = lower_bound(db.begin(), db.end(), input, compare) - db.begin();
if(!check(input, db[left])) return 0;
int l = left;
int r = db.size() - 1;
while(l < r){
const int mid = l + (r - l)/2;
check(input, db[mid]) ? l = mid + 1 : r = mid;
}
if(l == db.size() - 1 && check(input, db[l])) l++;
return l - left;
}
vector<int> solution(vector<string> info, vector<string> query) {
Init();
for(const string& in : info){
vector<string> input = stringsplit(in);
struct apply tmp = {mmap[input[0]], mmap[input[1]], mmap[input[2]], mmap[input[3]], stoi(input[4])};
db.push_back(tmp);
}
sort(db.begin(),db.end(),compare);
vector<int> ans;
for(const string& in : query){
vector<string> input = stringsplit(in);
vector<struct apply> tmp;
vector<int> lang, type, career, food;
int score = stoi(input[7]);
if(input[0] != "-") lang.push_back(mmap[input[0]]);
else lang = {0, 1, 2};
if(input[2] != "-") type.push_back(mmap[input[2]]);
else type = {0, 1};
if(input[4] != "-") career.push_back(mmap[input[4]]);
else career = {0, 1};
if(input[6] != "-") food.push_back(mmap[input[6]]);
else food = {0, 1};
for(int& l : lang){
for(int& t : type){
for(int& c: career){
for(int& f : food){
tmp.push_back({l, t, c, f, score});
}
}
}
}
int sum = 0;
for(struct apply& para : tmp){
sum += cal(para);
}
ans.push_back(sum);
}
return ans;
}
배운점
처음에 구조체에서 언어, 직군, 경력, 소울푸드를 문자열로 관리하니 효율성에서 2개는 맞고, 2개는 시간초과가 났다. 전체적인 알고리즘의 시간복잡도는 빠듯해도, 안으로 들어올거라 생각해서 어디서 생각보다 더 큰 시간이 발생했는지 찾았다. 문제는 문자열이었다. 구조체에서 문자열이 많이쓰이다보니, 구조체를 생성하면서 복사하는 과정?으로도 생각보다 많은 리소스는 사용했다. 문자열을 정수형으로 변환하여 해결했다.
또한, 다른 사람의 풀이를 보니 unordered_map을 이용하여 해결하는 것이 가장 효율적인 방법같다. 나는 효율성 테스트에서 평균적으로 500ms가 나오고, 가장 큰 값은 약 700ms가 나오는데 해당 풀이는 안정적이게 모두 300 ~ 400ms이하가 나온다.
간단하게 그 알고리즘에 대해 설명하면, 자료구조는 unordered_map<string, vector
이제 query를 순회하며 각 점수리스트에서 이분탐색을 진행한다.