(출처) https://programmers.co.kr/learn/courses/30/lessons/72412
템플릿 쿼리 만들기
query들이 주어졌을 때 각 query에 일치하는 info가 몇 개나 되는지 카운팅 해주어야 하는 문제이다.
query 배열이 최대 100,000개 들어올 수 있고, info 배열은 50,000개가 들어올 수 있으므로 모든 쿼리에 대하여 info를 전부 하나씩 매칭해보는 것은 100,000 * 50,000으로 당연히 시간초과가 날 것 같았다.
query 배열과 info 배열을 직접 1:1 비교하면서 무식하게 카운팅 하는 것은 중복계산을 처리할 수 없기 때문에 굉장히 비효율적이다.
따라서 차라리 query로 들어올 수 있는 모든 경우를 먼저 계산하고 (쿼리 템플릿을 만드는 느낌), 만들어놓은 쿼리 템플릿과 info 배열을 매칭하여 미리 카운팅을 진행하고, 이후 query 입력이 들어오면 곧바로 값을 리턴하는 방식으로 진행하기로 하였다.
쿼리 템플릿은 ' - ' 의 경우까지 포함하여 각 언어, 직군, 경력, 소울푸드가 4 ,3 ,3 ,3 개씩 올 수 있으므로 총 108개가 된다.
진행과정은 108개의 쿼리 템플릿을 미리 만들고 각 info를 순회하며 쿼리에 맞는 info를 발견하면 해당 info의 점수를 쿼리 템플릿에 따로 보관한다.
모든 info에 대한 순회가 종료됐다면, 이후 쿼리 템플릿마다 따로 보관하고 있는 점수들을 정렬한 후 lower_bound로 접근하여 특정 점수 이상의 목록의 개수가 몇 개인지 구하면 된다.
쿼리 템플릿을 info 배열과 매칭하는데 108 * 50000 번의 연산횟수가 필요하고, 또 실제 입력 query 배열과 쿼리 템플릿을 매칭하여 순회하는 것에 108 * 100000 의 연산횟수가 필요하게 된다
두 연산을 합쳐도 1억 미만의 반복 연산이므로 충분히 풀 수 있을 것 같았다.
코드(시간초과)
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <sstream>
using namespace std;
string lang[4] = {"cpp","java","python","-"};
string job_group[3] = {"backend", "frontend", "-"};
string career[3] = {"junior", "senior", "-"};
string food[3] = {"chicken", "pizza", "-"};
string *q[4] = {lang, job_group, career, food};
unordered_map<string,int> um;
vector<pair<vector<int>,multiset<int>>> num_case;
void making_case(vector<pair<vector<int>,multiset<int>>>& num_case) {
for(int a = 0; a < 4; a++) {
for(int b = 0; b < 3; b++) {
for(int c = 0; c < 3; c++) {
for(int d = 0; d < 3; d++) {
pair<vector<int>,multiset<int>> temp;
temp = {{a,b,c,d},multiset<int>()};
num_case.push_back(temp);
}
}
}
}
}
vector<int> solution(vector<string> info, vector<string> query) {
vector<int> answer;
stringstream ss;
making_case(num_case);
for(int i = 0; i < num_case.size(); i++) {
for(int j = 0; j < info.size(); j++) {
string temp_str;
ss.clear();
ss.str("");
ss.str(info[j]);
for(int k = 0; k < 5; k++) {
//모든 info 검사가 끝나고 set에 정렬해서 등록
if(k == 4) {
ss >> temp_str;
num_case[i].second.insert(stoi(temp_str));
break;
}
string temp = q[k][num_case[i].first[k]];
ss >> temp_str;
if(temp == "-" || temp == temp_str) continue;
else break;
}
}
}
for(int i = 0; i < query.size(); i++) {
for (int j = 0; j < num_case.size(); j++) {
string temp_str;
ss.clear();
ss.str("");
ss.str(query[i]);
for(int k = 0; k < 5; k++) {
if(k == 4) {
ss >> temp_str;
auto lb = num_case[j].second.lower_bound(stoi(temp_str));
int result = 0;
for(auto iter = lb; iter != num_case[j].second.end(); iter++) result++;
answer.push_back(result);
break;
}
ss >> temp_str;
if(temp_str == "and") ss >> temp_str;
string temp = q[k][num_case[j].first[k]];
if(temp_str != temp) break;
}
}
}
return answer;
}
int main(){
vector<string> info = {"java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"};
vector<string> query = {"java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"};
vector<int> answer = solution(info, query);
for(int i = 0; i < answer.size(); i++) {
cout << answer[i] << " ";
}
return 0;
}
시간초과.. 이 후 최적화(비트마스킹)
막상 로직을 코드로 올려보니 지저분한 곳도 너무 많고 특히나 시간복잡도를 계산할 때 간과하고 넘어갔던 부분도 존재했다.
쿼리 템플릿을 info 배열과 매칭하면, 매칭 과정에서 두 문자열을 검사하는 과정이 필연적으로 포함되게 되는데 이 과정의 반복 연산 계산을 간과한 것이다.
(또한 굳이 multiset을 써보겠다고 쿼리 템플릿에 정렬을 유지한 채로 수를 저장해가는 자료구조를 이용해 봤는데 이 과정에서도 불필요한 연산이 들어갔다.)
코드를 보면 처음 계산했던 연산횟수 (108 * 50000 + 108 * 1000000) 과는 다르게, info와 매칭하는 부분에서만 108 * 50000 * 5 * (세부문자열 비교 평균 4~5?) = 1억이상 의 반복 연산이 들어가게 되었다.
따라서 굳이 쿼리템플릿(108개)을 각 info와 매칭 시키는 형태로 진행하지 않고, 그냥 info 배열을 보고 알맞은 쿼리템플릿을 찾아가 등록하는 식으로 진행해 보기로 하였다.
각 info는 4가지의 필드(언어,직군,경력,소울푸드)가 각각 ' - ' 이거나 ' - ' 이지 않거나로 나눠져 총 2^4 = 16가지의 템플릿과 매칭된다.
info 하나당 굳이 모든 템플릿 108개를 전부 매칭하지 않고, info가 해당하는 템플릿 16개를 직접 찾아가는 과정으로 최적화를 진행하는 것이다.
또한 위와 같은 방식으로 진행하면 문자열을 비교해 주는 과정도 자연스럽게 생략되기 때문에 훨씬 효율적으로 동작한다.
수의 보관은 그냥 multiset이 아닌 동적배열 vector를 이용하기로 하였다.
코드(최적화)
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map<string, int> um;
vector<int> num_case[4][3][3][3];
vector<int> solution(vector<string> info, vector<string> query) {
um["-"] = 0;
um["cpp"] = 1; um["java"] = 2; um["python"] = 3;
um["backend"] = 1; um["frontend"] = 2;
um["junior"] = 1; um["senior"] = 2;
um["chicken"] = 1; um["pizza"] = 2;
vector<int> answer;
for(int i = 0; i < info.size(); i++) {
stringstream ss;
ss.str(info[i]);
string lang_tem, group_tem, career_tem, food_tem;
string *str_p[4] = {&lang_tem, &group_tem, &career_tem, &food_tem};
int score;
ss >> lang_tem >> group_tem >> career_tem >> food_tem >> score;
for(int i = 0; i < (1<<4); i++) {
vector<int> temp (4,0);
for(int j = 0; j < 4; j++) {
if(i & (1 << j)) temp[j] = um[*str_p[j]];
}
num_case[temp[0]][temp[1]][temp[2]][temp[3]].push_back(score);
}
}
for(int a = 0; a < 4; a++) {
for(int b = 0; b < 3; b++) {
for(int c = 0; c < 3; c++) {
for(int d = 0; d < 3; d++) {
sort(num_case[a][b][c][d].begin(), num_case[a][b][c][d].end());
}
}
}
}
for(int i = 0; i < query.size(); i++) {
stringstream ss;
ss.str(query[i]);
string lang_tem, group_tem, career_tem, food_tem, tem;
int score;
ss >> lang_tem >> tem >> group_tem >> tem >> career_tem >> tem >> food_tem >> score;
auto iter = lower_bound(num_case[um[lang_tem]][um[group_tem]][um[career_tem]][um[food_tem]].begin(),
num_case[um[lang_tem]][um[group_tem]][um[career_tem]][um[food_tem]].end(),
score);
int result = num_case[um[lang_tem]][um[group_tem]][um[career_tem]][um[food_tem]].end() - iter;
answer.push_back(result);
}
return answer;
}
int main(){
vector<string> info = {"java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"};
vector<string> query = {"java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"};
vector<int> answer = solution(info, query);
for(int i = 0; i < answer.size(); i++) {
cout << answer[i] << " ";
}
return 0;
}기억하고 싶은 점
비트마스킹은 부분집합을 구하는 작업등을 수행해야 할 때 유용하다.
(각 요소에 대해서 선택을 하는 경우, 선택을 하지 않는 경우로 나누어지는 조합을 구할 때 유용하다. 어떻게 보면 비트표현이 각 요소를 선택하는 과정이랑 굉장히 닮았다.)
lower_bound 및 upper_bound의 활용도 여러 번 해보면서 익숙해져야겠다. 사용법에 익숙지 않아서 구글링 해보는데 시간이 너무 오래 걸림.
