2021 KAKAO BLIND RECRUITMENT-순위 검색 -C++

문제바로가기
이번문제는 이분탐색을 약간 쓰라고 힌트를 말로 준 문제, 하지만 이 문제는 이블로그
를 참고해서 풀었다.

일단 역시 문제의 흐름을 통해서 어떻게 풀지 생각해보자
info에서 java backend junior pizza 150이 있다.
query에서 java - junior pizza 100이 있다고 쳐보자.
일단 문제의 흐름대로 가보면 - 에 해당하는 부분을 바꿔서
java backed junior pizza 100
java frontend junior pizza 100
이렇게 두개를 만들어서 info에 해당하는 java backend junior pizza과 동일한 쿼리를 찾고 100과 150을 비교하면 될것이다.

그런데 문제가 일단, - - - - 4자리가 있으므로 만약 이렇게 된다면
0 -> java, python
1 -> backed, frontend
2 -> junior ,senior
3 --> pizza, chicken
을 만든 다음에, 그후에 이걸 또 1번인덱스가 - 일때 또 for문을 2번돌아서 쿼리를 만드는 복잡한 방식을 거쳐야할 것이다.

그래서 쿼리를 만들기보다는, info를 가지고 만들수있는 경우의 수를 생각해보는것이다.
java backed junior pizza
java backed junior -
java backed - pizza
java backed - -
...
이런식으로 말이다. 그 다음에, 해당하는 쿼리를 가지고 해당 경우의 수가지고 판단하는것이다.

그런데 문제가 있는데, 이게 시간복잡도가 너무 오래걸린다.
info에서 한개가 java backed junior pizza로 최대 갯수인 50,000개가 있다고 치자. 그러면 java backed junior pizza 에다가 vectorv에 숫자 5만개가 들어가있다.
근데 쿼리갯수가 최대가 100,000개니까 여기서 만약 java backed junior pizza로 10을 줘버리면 100,000 * 50,000니까 이걸 linear 탐색을 하게되면 무조건 시간초과가 나오게 된다.

그래서 여기서 문제에서 힌트를 준게 몇점 이상을 찾으라는것이다. 이건 ~이상을 찾으라는건 이분탐색인 lower_bound를 사용하라고 힌트를 준것과 같다.

그래서 코드를 살펴보면

void addCases(vector<string> words, int score, int tmp) {
  if (v.size() == 4) {
      string s = "";
      for (int i = 0; i < 4; i++) {
          s += v[i];
      }
      um[s].push_back(score);
      return;
  }

     v.push_back(words[tmp]);
      addCases(words, score, tmp + 1);
      v.pop_back();

      v.push_back("-");
      addCases(words, score, tmp + 1);
      v.pop_back();
}

이부분은 이제 경우의 수를 만드는것이다. words에는 java backed junior python이 들어가있다.
그 다음에 sort로 정렬을 해주고

                ```

for(auto it = um.begin(); it !=um.end();++it){
sort(it->second.begin(),it->second.end());
}

                              
lowerbound를 사용하면된다.
  
  정답코드

#include
#include
#include
#include <unordered_map>
#include

using namespace std;
vectorv;
unordered_map<string, vector> um;

void addCases(vector words, int score, int tmp) {
if (v.size() == 4) {
string s = "";
for (int i = 0; i < 4; i++) {
s += v[i];
}
um[s].push_back(score);
return;
}

   v.push_back(words[tmp]);
    addCases(words, score, tmp + 1);
    v.pop_back();

    v.push_back("-");
    addCases(words, score, tmp + 1);
    v.pop_back();

}

vector solution(vector info, vector query) {
vector answer;
vector words(5);
for (auto str : info)
{
istringstream iss(str);// 지원자의 정보를 스트림으로 변형시켜 공백 기준으로 나눌때 간단히 나눠준다.
iss >> words[0] >> words[1] >> words[2] >> words[3] >> words[4];
addCases(words, stoi(words[4]),0);
}

for(auto it = um.begin(); it !=um.end();++it){
sort(it->second.begin(),it->second.end());
}

for (auto q : query)
{
    int idx = 0;
    istringstream iss(q);
    iss >> words[0] >> words[4] >> words[1] >> words[4] >> words[2] >> words[4] >> words[3] >> words[4];
    vector<int> scores = um[words[0]+words[1]+words[2]+words[3]];
    if (scores.empty())
    {
        answer.push_back(0);
        continue ;
    }
    //sort(scores.begin(),scores.end()); 여기서 정렬을 하면 100,000번 하게 될 수도 있다.....
    idx = lower_bound(scores.begin(), scores.end(), stoi(words[4])) - scores.begin();
    answer.push_back(scores.size() - idx);//총인원수에서 조건보다 낮은 점수 인원 빼주기
}
return answer;

}