[프로그래머스] 순위 검색 Python3

https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=python3# 

프로그래머스

Hash 자료구조와 이진탐색을 이용하여 효율성을 맞혀야 하는 문제이다. 어려웠따..
백준 환경에 익숙해져있는 상태인데, 기업 코딩 테스트를 위해 프로그래머스 환경에서 좀 연습을 해야겠다 

딱봐도 for문으로 빡빡 돌려서 구하면 시간 초과날 것 같다 ㅎㅎ 

i) dictionary 구성하기 
이 딕셔너리를 구성하는 것이 문제해결의 포인트이다. 

info 값으로 , 
java backend junior pizza 150 이 주어졌을 때 , 
맨 마지막 코딩테스트 점수는 value로 , 
언어-직군-경력-소울 푸드 조합은 key로 사용한다. 
왜???
결국 문제에서 요구하는 사항은 ~~한 조건을 가졌을 때 , 코딩테스트 점수가 ~점이상인 지원자의 수를 리턴해야 하기 때문이다. 

다음과 같은 경우의 수가 발생한다. 이는 파이썬 내장 라이브러리인 itertools 의 combinations로 구현했다. 

또 한가지 생각해볼 것은,
- - - - 의 경우, 여러가지 info 에 해당할 수 있다. -> 즉 해당 쿼리에 대해 복수개의 경우가 검색되어야 한다. 
이런 경우를 대비하여 defaultdict을 list로 초기화 할 것이다.
key 의 값은 만드는 아이디어가 여러가지가 있겠지만, 문자열로 이어붙였다. 

그렇다면 info_table 의 모습은 다음과 같다. 
{"----": [150,210,120,260,80,50], "javabackendjuniorpizza":[150], "-backendjuniorpizza":[150] , ... }

ii) Python bisect_left 함수 

list 에서 가장 맨 먼저 등장하는 원소의 인덱스를 반환한다. 

[예시] 
array = [100, 200, 200, 300, 400, 500]

index = bisect_left(array, 200) // index 는 1 이다. 

예시로 쿼리에 "java and backend and junior and pizza 100"
이 나온다면 
이 쿼리로 info_table에 접근하기 위한 key 를 문자열로 만들어 준다면 "javabackendjuniorpizza" 가 될것이다. 

접근하게 된다면 
info_table["javabackendjuniorpizza"] 는 [150,80] 이렇게 있을것인데, 
리스트 형태의 value를 정렬해주어야 이진탐색을 할 수 있다 
bisect_left로 값을 찾기 위해 미리 value 부분을 오름차순으로 정렬해놓았다. 

for value in info_table.values():
        value.sort() # 이진 탐색을 위해 정렬

그렇다면 value 값은 [80, 150] 이다. 
총 길이는 2 이다. 
그리고 bisect_left(value, 100) 을 하면 인덱스로 1이 나올 것이다. 100 이상인 150부터 카운트를 하면된다. 
따라서 이 쿼리에 대한 값은 1이 된다. 

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

def solution(info, query):
    answer = []
    info_table = defaultdict(list)
    
    for i in info:
        data = i.split()
        score = int(data[-1])
        conditions = data[:5]
        for k in range(5):
            combi = list(combinations([0, 1, 2, 3], k))
            for case in combi:
                head = []
                for c in range(4):
                    if c in case:
                        head.append("-")
                    else:
                        head.append(conditions[c])
                key = "".join(head)
                info_table[key].append(score)      
    

    for value in info_table.values():
        value.sort() # 이진 탐색을 위해 정렬 
    
    for i in range(len(query)):
        count = 0 
        q = query[i].replace("and", " ").split()
        target_key = "".join(q[:-1])
        target_score = int(q[-1])
        count = 0 
        if target_key in info_table:
            target_list = info_table[target_key]# score list 
            index = bisect_left(target_list, target_score)
            count = len(target_list) - index 
        answer.append(count)
    
    return answer