프로그래머스: 순위 검색(Level 2)

프로그래머스: 순위 검색(Level 2)

 

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

 

문제 설명

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

풀이 방법

본 문제는 정확성과 효율성을 모두 통과해야 된다.

정확성을 통과하는 것은 어렵지 않다.

모든 info에 대해서 query와 각각 비교하면 된다. 하지만 이 방식은 효율성을 통과하지 못한다.

 

갈피를 잡지 못해서 카카오 테크 블로그에서 힌트를 참조해서 풀었다.

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

카카오 테크 블로그에서는 주어진 info 배열로 만들 수 있는 모든 조합을 미리 만들어서 풀었다.

예를 들어, "java backend junior pizza 150" info는 [java, -], [backend, -], [junior, -], [pizza, -] 에서 각각 한 개씩을 추출해서 총 16(2x2x2x2)가지의 조합을 만들 수 있다. 이런 방법으로 모든 조합을 만들어서 딕셔너리 key로 저장한 뒤 score를 배열로 저장했다. 

이런 방식 딕셔너리를 미리 구축해 놓으면, query가 주어졌을 때 dict[query]를 통해서 해당 조건에 만족하는 사람들의 점수를 배열로 한 번에 얻을 수 있다.

query 조건을 만족하는 사람들의 점수를 배열로 받았을 때, for loop으로 query에서 주어진 score와 비교하면 시간 초과로 통과하지 못한다. 사람들의 점수를 담은 배열을 정렬한 뒤에 이진탐색으로 찾아야 효율성을 통과할 수 있다.

이진 탐색의 경우 bisect 라이브러리에서 bisect_left()를 사용했다. 직접 구현하는 코드도 매우 간단하다. 아래에 따로 첨부하겠다.

 

라이브러리 사용한 풀이

bisect_left()를 구현해서 푼 풀이