[Python] 프로그래머스. 2021 카카오 recruit - 순위 검색 (Level 2)

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

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

 

정확성 기준으로는 Level 2가 맞지만, 효율성을 생각하면 절대 Level 2 문제는 아닌 듯하다.

작년에 이 문제를 풀 때에도 효율성은 통과하지 못했고, 카카오 공식 풀이와 다른 분들의 포스트를 보고서야 풀 수 있었다.

 

1. 카카오 공식 홈페이지에서 설명한 16가지 경우의 수 생성하기 - DFS

2. 주어진 배열에서 효율적으로 검색 - 이진탐색.

 

Python은 그나마 combinations, bisect 내장 라이브러리를 사용할 수 있어서 직접 구현해내는 건 어느 정도 건너뛸 수 있었지만

시험장에서 느꼈던 체감 난이도는 굉장히 높았었다.

 

 

 

 

코드 마지막에 bisect_left를 사용한 이유

 

ex) [1,2,2,3,4,4,5,6,7] 에서 4 이상의 값을 가진 데이터는 몇 개인지 파악하려고 할 때

bisect_left는 동일한 데이터가 있을 경우 해당 index의 왼쪽 값을 반환한다.

즉 4의 위치는 index 4와 5로 2개이지만,
bisect_left 메소드는 동일한 데이터가 있을 경우 왼쪽 index를 반환하므로 4를 리턴한다.

 

전체 데이터 개수 len() = 9개, bisect_left로 찾아낸 위치 = 4.

따라서 9 - 4 = 5가 "4보다 큰 데이터의 개수" 가 된다.

 

Bisect 공식문서

docs.python.org/ko/3/library/bisect.html#bisect.bisect_left

bisect — 배열 이진 분할 알고리즘 — Python 3.9.1 문서

 

공식 해설

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

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설