[프로그래머스] 파이썬 _ 순위 검색 (2021 KAKAO BLIND)

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

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

 

문제유형 : 딕셔너리(해시), 이진탐색

 

문제풀이 :

 

- 우선 내가 푼 방식으로는 정확도는 모두통과했지만 효율성에 통과하지못해서 결국 카카오 공식블로그에 나와있는 풀이힌트를 보고 품

 

< 내가 푼 방식 >

각각의 키워드 (java, back, ---) 를 키값으로하고 해당되는 사람을 값(집합)로 갖는 딕셔너리를 만든다.

조건을 돌때마다 각 키워드로부터 해당하는 사람의 값을 집합으로 가져오고 교집합을 구해나간다.

점수의 경우 ~이상일때 라는 조건에 해당해야하므로 추가 함수를 만들어서 해결한다. ( 몇점 이상에 해당하는 키값들의 값들을 합집합하여 하나로 만듬)

 

---효율성 통과 못함---

 

< 블로그에 나온 방식 >

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

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

 

어떤 한명의 조건이 있을때, 그 사람이 해당할 수있는 모든 그룹을 만들고 그 그룹에 해당 사람을 추가시킨다.

 

==== 여기서 몇점 이상의 사람을 찾는 과정을 이진탐색으로 풀어야 효율성을 통과할 수 있다 ====

X점 이상 맞은 지원자를 찾기 위해 해당 그룹의 최저점, 혹은 최고점부터 순차적으로 검색한다면 여전히 오랜 시간이 걸리게 됩니다.

이때, 숫자가 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있습니다.

이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound를 이용하면 됩니다.

 

 

 “java backend junior pizza 150” 지원자의 경우 다음과 같이 16가지 그룹에 속하게 된다. 

•  

  

• 따라서 위 16가지 경우를 키로하고 점수배열을 값으로 하는 딕셔너리를 만든다.
• 딕셔너리내 모든값들을 정렬한다. (점수들을 오름차순으로 정렬) -> 점수의 이분탐색을 위해
• 딕셔너리에서 쿼리에 해당하는 키값으로 점수배열을 찾는다. 딕셔너리이므로 O(1)을 통해 찾을 수 있다.
  • 찾은 점수배열은 해당 쿼리를 만족하는 사람들의 점수가 오름차순 정렬되어 담겨있다.
  • 여기서 이제 X점 이상하는 점수가 어디서부터 시작하는지를 이진탐색을 기반으로한 lower bound알고리즘을 통해 찾아야한다.
  • 이때 직접 구현하는것보다 파이썬 bisect라이브러리의 bisect_left()함수를 이용하면 쉽게 lower bound를 구현할 수 있다.

정답코드 :

from bisect import bisect_left
from collections import defaultdict
from itertools import combinations


# 모든 경우의수를 만들어 해당 경우의 수를 키값으로 하는 딕셔너리에 score를 저장한다.


def solution(info, query):
    answer = []
    dic = {}
    comb = [0, 1, 2, 3]
    for i in info:
        person = i.split()
        conditions = person[:-1]
        score = int(person[-1])
        for j in range(5):
            for k in list(combinations(comb, j)):
                temp = conditions.copy()
                for idx in k:
                    temp[idx] = '-'
                key = ''.join(temp)
                if key in dic:
                    dic[key].append(score)
                else:
                    dic[key] = [score]
    # print(dic)
    for value in dic.values():  # 딕셔너리 내 모든 값 정렬
        value.sort()

    for i in query:
        q_list = []
        for j in i.split():
            if j == 'and':
                continue
            q_list.append(j)

        target = int(q_list[-1])
        key = ''.join(q_list[:-1])

        if key in dic:
            hubo_list = dic[key]

            index = bisect_left(hubo_list, target)
            answer.append(len(hubo_list) - index)
        else:
            answer.append(0)
            continue

    # print(answer)
    return answer

- 근데 여기서 진짜 이해가 안가는것이 있다.

딕셔너리내 모든값을 정렬한는 부분에서,, 전체를 한번에 정렬하지않고 쿼리를 돌때마다 해당 쿼리를 키값으로 하는 점수배열을 가져온후 그 점수 배열을 정렬하는식으로 풀면 전체 점수배열을 정렬하지않아도 되고 쿼리에 해당하는 점수배열들만 정렬하면 되므로 더 빠를것이라고 생각했는데 이렇게하면 시간초과가 난다...

 

단순히 정렬자체만 놓고보면 더 적은횟수로 정렬하는것이지만, 반복문안에서 배열을 정렬하는것이 뭔가 시간초과가 나는 원인이 있는것같다..