[프로그래머스 72412] 순위 검색 (C++)

A. 문제설명

문제에 대한 자세한 설명은 링크 참조

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

코딩테스트 연습 - 순위 검색

 

1. 지원자의 지원 항목을 아래 기준에 따라 4가지로 분류

코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

2. 이에 추가로 코딩테스트 점수를 반영

3. 이러한 지원자 정보를 가지고, 아래와 같은 형태의 문의사항을 가지려고 함

코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

4. 이때, 지원자 정보 목록과 문의 목록이 주어졌을 때 이 조건들을 만족하는 인원의 수를 구하라

 

B. 접근법

정렬 + 이진 탐색

 

먼저, 개발언어/직군/경력/소울푸드를 기준으로 인원을 나누고 그 안에 벡터로 점수 리스트를 모음. 문제에서 요구하는 것은 문의사항 쿼리에 해당하는 인원의 수이기 때문에 정렬되어 기존 인원 정보들이 누락되더라도 상관없음.

각각의 개발언어/직군/경력/소울푸드별 체크 벡터 chkVec[3][2][2][2]로 인원들의 점수를 정렬하고 이에 대한 검색을 수행할 때, lower_bound() 함수를 이용하여 이진탐색으로 다시 한번 가지치기를 해서 연산을 수행.

* 효율성 테스트에서 연산 횟수가 문제 조건인 info 배열이 최대 50,000개, query 배열이 최대 100,000개이기 때문에 이를 brute force로 모두 탐색시 효율성 테스트에서 실패한다. 이를 위해 쿼리별로 개발언어/직군/경력/소울푸드별 체크 벡터를 사용하고 이진 탐색을 사용하여 연산횟수를 최소로 줄여야 한다.

 

C. 풀이

1. 개발언어/직군/경력/소울푸드를 기준으로 인원 나누어 점수 벡터에 삽입

2. 체크 벡터 chkVec[3][2][2][2] 인원들의 점수를 정렬

3. lower_bound() 함수로 점수구간 이진 탐색, 쿼리 조건의 점수위치 iterator 찾아 갯수 계수

 

D. 내 코드