[프로그래머스 | Lv2] 순위 검색 (Python) - 2021 KAKAO BLIND RECRUITMENT

 

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

프로그래머스

 

각 info에 대해 탐색될 수 있는 모든 경우의 수를 만들어준다.

 

예를 들어 [java, backend, junior, pizza]의 선택을 가진 사람이 있다면,

[java, backend, junior, pizza],

[-, backend, junior, pizza],

[java, -, junior, pizza],

...

[-, -, -, -]

👆위의 모든 경우를 만들어주는 것이다.

 

그 후 query를 탐색하면서 정답을 하나씩 추가해주면 된다.

 

# 프로그래머스 72412: 순위 검색 (2021 KAKAO BLIND RECRUITMENT)

from itertools import combinations

def solution(info, query):
    answer = [0] * len(query)
    
    dic = {("-", "-", "-", "-"): []}
    for i in info:
        i = i.split()

        pick = tuple(i[:4])
        score = int(i[4])
        
        if pick in dic:
            dic[pick].append(score)            
        else:
            dic[pick] = [score]

        dic[("-", "-", "-", "-")].append(score)

        for j in range(1, 4):
            combi = list(combinations(range(4), j))
            for c in combi:
                tmp = ["-"] * 4
                for k in list(c):
                    tmp[k] = i[k]
                tmp = tuple(tmp)
                
                if tmp in dic:
                    dic[tmp].append(score)
                else:
                    dic[tmp] = [score]
    
    for i in range(len(query)):
        q = query[i].replace("and", "").split()
        con = tuple(q[:4])
        sc = int(q[4])
        
        if con in dic:
            for s in dic[con]:
                if s >= sc:
                    answer[i] += 1
        
    return answer

 

정확성 테스트는 통과했지만, 효율성 테스트에서 실패했다.

 

각 info에 대해 탐색될 수 있는 모든 경우의 수를 만들어주는 부분을 조금 다듬었고,

(before - 직접 ("-", "-", "-", "-") 등의 튜플을 만들어서 넣어줌

after - combinations의 범위를 늘려 해당 튜플 자체를 넣어줌)

딕셔너리 내의 리스트를 내림차순으로 정렬하여

목표 점수보다 작으면 바로 반복문을 빠져나오도록 했다.

 

# 프로그래머스 72412: 순위 검색 (2021 KAKAO BLIND RECRUITMENT)

 from itertools import combinations

 def solution(info, query):
     answer = [0] * len(query)

     dic = {}
     for i in info:
         i = i.split()
         pick = tuple(i[:4])
         score = int(i[4])

         for j in range(5):
             combi = list(combinations(pick, j))
             for c in combi:
                 if c in dic:
                     dic[c].append(score)
                 else:
                     dic[c] = [score]

     for key in dic:
         dic[key].sort(reverse = True)

     for i in range(len(query)):
         q = query[i].replace("and", "").replace("-", "").split()

         if len(q) == 1:
             con = ()
         else:
             con = tuple(q[:-1])

         sc = int(q[-1])

         if con in dic:
             for s in dic[con]:
                 if s < sc:
                     break
                 answer[i] += 1

     return answer

 

여전히 시간 초과

그래서 이진 탐색을 도입했다.

점수 이상의 값을 찾으면 되기 때문에 파이썬의 bisec_left 모듈을 이용했다.

 

# 프로그래머스 72412: 순위 검색 (2021 KAKAO BLIND RECRUITMENT)

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    answer = [0] * len(query)
    
    dic = {}
    for i in info:
        i = i.split()
        pick = tuple(i[:4])
        score = int(i[4])

        # 각 info에 대해 탐색될 수 있는 모든 경우의 수를 딕셔너리에 추가 {(query):[score]}
        for j in range(5):
            combi = list(combinations(pick, j))
            for c in combi:
                if c in dic:
                    dic[c].append(score)
                else:
                    dic[c] = [score]
    
    for key in dic: # 이진 탐색을 위한 정렬
        dic[key].sort()

    for i in range(len(query)):
        q = query[i].replace("and", "").replace("-", "").split()
        
        # query
        if len(q) == 1:
            con = ()
        else:
            con = tuple(q[:-1])
        
        # score
        sc = int(q[-1])

        # Lower Bound
        if con in dic:
            pos = bisect_left(dic[con], sc)
            answer[i] = len(dic[con]) - pos
        
    return answer

 

😂 힘들게 성공했다..