[programmers][2021카카오공채] 순위 검색

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

---

query가 100,000 infos가 50,000.

query 문자열에 맞게 infos에 맞는 조건을 찾아서 정답을 구하기엔 시간이 부족하다.

개발언어가 3개. 직군 2개. 경력 2개. 소울푸드 2개.

3x2x2x2 = 24개의 조합에 맞는 score들을 저장해두면 시간을 확 줄일 수있다.

scores[개발언어][직군][경력][소울푸드] = 점수들 배열.

 

만약 query에 개발언어가 상관없다면 scores[0~3][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다.

query에 개발언어가 java라면 scores[java 인덱스][직군][경력][소울푸드]의 scores 조건에 맞는 점수들의 수를 정답에 포함시킨다.

scores 조건에 맞는 점수들의 개수는 이분탐색으로 구할 수 있다. 이분탐색을 위해 점수들 배열은 오름차순 정렬되어 있어야 한다.

 

시간복잡도는 query가 N, infos가 M이면 O(NlogM).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/2021%EC%B9%B4%EC%B9%B4%EC%98%A4%EA%B3%B5%EC%B1%84/%EC%88%9C%EC%9C%84%20%EA%B2%80%EC%83%89.cpp