[파이썬, 프로그래머스] 순위 검색 - 2021 KAKAO BLIND RECRUITMENT

문제

 

문제 바로가기: [프로그래머스] 순위 검색 - 2021 KAKAO BLIND RECRUITMENT

---

풀이

 

#단순하게 하나하나 비교하여 풀이한다면, 50,000 * 100,000으로 매우 많은 연산 때문에 효율성에서 시간초과가 발생할 것이다

#LV2치고는 난이도가 조금 높지 않았나 생각한다..

#조합, 딕셔너리(해쉬), 이진 탐색(lower bound)

 

1. 먼저 info의 값을 모든 조합으로 나누어 { 조합: 점수 } 형태로 딕셔너리에 저장합니다. 예를 들어 info가 ["java backend junior pizza 150" ]라면, 아래와 같이 16가지 조합이 나오며, 모두 딕셔너리에 저장해줍니다

	150
java	150
backend	150
junior	150
pizza	150
java backend	150
java junior	150
java pizza	150
backend junior	150
backend pizza	150
junior pizza	150
java backend junior	150
java backend pizza	150
java junior pizza	150
backend junior pizza	150
java backend junior pizza	150

   1-1. 이렇게 하는 이유는 query가 "java and - and - and - 150" 일 때  빠르게 java만을 이용해 딕셔너리에서 몇 명이 해            당되는지 찾을 수 있습니다

 

2. 이어서 info가 ["java backend junior pizza 150", "java backend junior chicken 80" ]라면, 이어서 딕셔너리에 저장해줍니다. 

"" (빈 문자열)	150, 80
java	150, 80
backend	150, 80
junior	150, 80
pizza	150
java backend	150, 80
java junior	150, 80
java pizza	150
backend junior	150, 80
backend pizza	150
junior pizza	150
java backend junior	150, 80
java backend pizza	150
java junior pizza	150
backend junior pizza	150
java backend junior pizza	150
chicken	80
java chicken	80
backend chicken	80
junior chicken	80
java backend chicken	80
java junior chicken	80
backend junior chicken	80
java backend junior chicken	80

3. 위의 과정처럼 먼저, 모든 info의 정보들을 딕셔너리에 저장해줍니다

 

4. 이제 query의 정보들을 이용합니다. query가 "java and backend and junior and - 100"라면, java backend junior를 바로위 2번 예시 딕셔너리에서 찾으면 150, 80 을 구해 2명임을 알 수 있습니다

     4-1. 하지만 구해야 되는건 특정 점수 이상이 몇 명 인지를 구해야 됩니다.

     4-2. 모든 점수를 비교해 특정 점수 이상이 몇 명인지 구한다면, 시간초과가 발생할 것입니다

 

5. 이 때, 이분 탐색을 이용해서 빠르게 해당 점수 이상이 몇 명인지 구할 수 있습니다

     (lower bound: 원하는 값 K 이상이 처음 나오는 위치를 찾는 과정)

    5-1. 150, 80, 100, 230 중에서 100 이상이 되는 수를 이진 탐색을 이용해 빠르게 찾을 때,

    5-2. 80, 100, 150, 230 처럼 먼저 정렬을 해줍니다

    5-3. 파이썬 메서드 bisect_left을 이용해 100이 들어갈 인덱스를 찾아주면, 인덱스 1이 반환됩니다 (lower bound)

          (같은 값이 있을 경우 가장 왼쪽의 인덱스를 반환)  

    5-4. (총 길이 - 반환된 인덱스) 4 - 1를 해주면, 최종적으로 100점 이상은 3명 이상임을 알 수 있습니다

          (총길이 구할 때 len()함수를 사용해도 되는데, 이것의 시간복잡도는 O(1)입니다)

---

코드

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    #먼저 딕셔너리에 모든 조합 넣기 { 조합: 점수 } 형태
    dictionary = {}
    for i in info:
        i = i.split(' ')
        for j in range(5): #조합 0개도 가능,  조합 0개일 때 딕셔너리에 ""빈문자열 형태로 저장
            combi = list(combinations(i[:4],j))
            for com in combi:
                str_value = " ".join(list(com))
                if str_value in dictionary:
                    dictionary[str_value].append(int(i[4]))
                else:
                    dictionary[str_value] = [int(i[4])]
    
    #이진탐색을 위해 미리 딕셔너리의 value값들 정렬
    for key in dictionary:
        dictionary[key].sort()
    
    answer = []
    for q in query:
        q = q.split(' and ')
        value = q[3].split(' ')
        q[3] = value[0]
        
        str_value = []
        for i in q:
            if i != '-':
                str_value.append(i)
        str_value = " ".join(str_value)
        
        if str_value in dictionary:
            result = dictionary[str_value]
            answer.append(len(result) - bisect_left(result, int(value[1])))
        else:
            answer.append(0)
            
    
    return answer

---

결과