2021 Kakao blind 72412 - 순위 검색(문자열 파싱, 비트마스킹, 이진탐색)

2021 Kakao blind 72412 - 순위 검색(문자열 파싱, 비트마스킹, 이진탐색)

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

- 문제에서 어려웠던 부분이 특정 조건에 해당 안되고, 모두 포함하는 조건을 어떻게 카운트할지 고민하다가, 해당 attribute가 'all'인 경우의 수를 담는 인덱스를 하나 더 만들어서 모두 카운트하는 방식으로 풀었다.

- 개발언어, 지원직군, 경력, 소울푸드, 점수를 담는 4차원 배열의 벡터(5차원) 을 만들었다. 0번 인덱스면 'all'조건을 담는 것이고 나머지 해당 인덱스는 해쉬맵을 통해서 해당 문자열이 파싱된 인덱스에 담아진다.

- 만들어 질 수 있는 모든 사람조건 경우의 수에 대해서 순회하도록 비트마스킹을 돌면서 해당 조건에 맞는 인덱스를 찾아 벡터에 넣어준다.

- 그 다음에 모든 벡터들을 오름차순으로 소팅을 해주면 해당 조건에 알맞는 사람들의 점수에 대해 이분탐색으로 기준 점수 이상의 인원의 수를 구할 수 있다. 간단하게 이더레이터 연산으로 (iterator)end() - (iterator)특정 점수의 하한 = (int)특정 점수 이상의 인원 수가 나온다

#include #include #include #include #include using namespace std; unordered_map umap{ {"-", 0}, {"cpp", 1}, {"java", 2}, {"python", 3}, {"backend", 1}, {"frontend", 2}, {"junior", 1}, {"senior", 2}, {"chicken", 1}, {"pizza", 2}}; vector parsedInfo[4][3][3][3]; vector solution(vector info, vector query) { string lang, pos, exp, food, etc; int score; for (string& str : info) { stringstream ss(str); ss >> lang >> pos >> exp >> food >> score; vector v = {umap[lang], umap[pos], umap[exp], umap[food]}; for (int i = 0; i < (1 << 4); ++i) { int idx[4] = {0}; for (int j = 0; j < 4; ++j) { if (i & (1 << j)) { idx[j] = v[j]; } } parsedInfo[idx[0]][idx[1]][idx[2]][idx[3]].push_back(score); } } for (int i = 0; i < 4; ++i) { for (int j = 0; j < 3; ++j) { for (int k = 0; k < 3; ++k) { for (int l = 0; l < 3; ++l) { sort(parsedInfo[i][j][k][l].begin(), parsedInfo[i][j][k][l].end()); } } } } vector ans; for (string& q : query) { stringstream ss(q); ss >> lang >> etc >> pos >> etc >> exp >> etc >> food >> score; vector& v = parsedInfo[umap[lang]][umap[pos]][umap[exp]][umap[food]]; int num = v.end() - lower_bound(v.begin(), v.end(), score); ans.push_back(num); } return ans; }

from http://ellerymoon.tistory.com/62 by ccl(A) rewrite - 2021-09-06 01:26:51