[PS] 순위 검색 (프로그래머스)

문제 링크

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

문자열 parsing과 dict(해쉬)의 중요성을 다시금 느끼는 문제였다.

느낀 점

• 파이썬 라이브러리 bisect
  • 이진 탐색을 해주는 라이브러리
  • bisect.bisect_left(arr, element, (start) ,(end))
    • arr(오름차순으로 정렬되어 있다고 가정)에 element를 넣는다면 어디에 위치할 지 index를 반환함. element 보다 작은 원소 뒤에 위치(element와 같은 원소보다는 앞(왼쪽)에 위치함)
    • bisect_right() 는 element 보다 큰 원소 앞에 위치
• 검색하기 전에 dict의 item들을 정렬하냐, 검색하면서 해당 item들을 정렬하냐 둘 중 후자가 시간이 덜 걸린다고 생각했다.
  • 그러나, (‘–seniorchicken’: 100 ‘–seniorchicken’: 150, ..) 등의 중복이 무수히 발생할 수 있다. (문제의 조건을 보면 ‘query 배열의 크기는 100,000 이하’ 지만 ‘언어’, ‘직군’, ‘경력’, ‘소울푸드’ 는 모두 보기가 3개 뿐이기 때문)
  • 그래서 검색 전에 정렬 시키는게 효율성 테스트에서 10배 정도 빨랐다.