[PRGRMS]72412번: 순위 검색

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

---

여러 해결 방법이 있지만 저는 시뮬레이션 + 이분 탐색으로 해결했습니다.

 

지원자의 4가지 항목에 대해 생길 수 있는 81가지(4x3x3x3)의 상태를 분기하여 리스트를 만듭니다.

그리고 지원자의 정보를 입력받을 때 마다 지원자의 정보가 조회될 수 있는 상태 리스트에 모두 지원자의 점수를 넣어습니다.

그리고 쿼리 수행전에 오름차순 정렬을 해놓습니다.

 

그러면 하나의 쿼리를 이분 탐색을 통해 해결할 수 있습니다.

시간 복잡도는 O(NlogM)입니다. (지원자의 수: N, 쿼리의 수 M)

---

코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%88%9C%EC%9C%84%20%EA%B2%80%EC%83%89.java