순위 검색 (Level 2)

문제

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

프로그래머스

 

풀이

 

지원자 정보를 저장하기 위해 infomap을 만들었다. defaultdict로 선언하여 value에 해당하는 값을 리스트로 초기화하였다.

infomap의 key는 info로 만드는데, 하나의 info는 총 16가지 경우의 수로 나눠진다. 

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

16가지의 경우의 수는 중복 조합을 구하는 함수인 product를 통해 구한다. itertools.product((True, False), repeat=4))를 선언하면,

[(True, True, True, True), (True, True, True, False), (True, True, False, True), (True, True, False, False), (True, False, True, True), (True, False, True, False), (True, False, False, True), (True, False, False, False), (False, True, True, True), (False, True, True, False), (False, True, False, True), (False, True, False, False), (False, False, True, True), (False, False, True, False), (False, False, False, True), (False, False, False, False)]

와 같은 배열이 만들어지게 되고, False인 곳에 '-'가 들어간다고 생각하면 된다.

 

이렇게 key를 만들었으면 infomap[key]에 info의 점수를 value로 저장한다. 지원자들의 info를 보다가 정보는 동일하지만 점수가 다르다면, 정보를 key로 하는 곳에 점수가 추가되는 방식이다. ex) 'javabackend--': [150, 80]

 

infomap의 value의 원소들을 오름차순으로 정렬한다. 그러면 infomap의 세팅이 완료된다.

 

infomap을 다 만들었으면, query를 돌아야 한다.

query의 구성요소인 q는 조건과 'and'로 구성되어 있으므로 and를 제거해주어야 한다. and를 제외한 나머지 것들로  infomap 검색에 사용할 key를 만든다.

q에 존재하는 점수보다 같거나 큰 지원자가 몇 명인지 구해야 하므로 q의 점수를 타겟으로 하여 infomap[key] 안에서 이진 탐색을 한다. 

 

이진 탐색을 할 때에는 직접 구현해도 되지만, 파이썬의 자랑인 bisect 라이브러리를 사용한다.

bisect 라이브러리에는 bisect_left와 bisect_right가 있다. 여기서는 bisect_left를 사용하는 것이 바람직하다.

인덱스를 구하였으면 infomap[key]의 길이에 인덱스를 빼서 인덱스 q의 점수보다 같거나 큰 지원자의 수를 구한다.

 

**참고**

1. 해당 값이 리스트에 있을 때

bisect_left : 해당 index 반환

bisect_right : 해당 index+1 반환

 

2. 해당 값이 리스트에 없을 때

bisect_left : 리스트에 해당값을 넣는다고 가정하였을 때, 오름차순으로 존재해야 할 index 반환

bisect_right : 리스트에 해당값을 넣는다고 가정하였을 때, 오름차순으로 존재해야 할 index 반환

 

 

import bisect, itertools, collections

def solution(info, query):
    infomap = collections.defaultdict(list)
    binarys = list(itertools.product((True, False), repeat=4))
    for inf in info:
        inf = inf.split()
        for binary in binarys:
            key = ''.join([inf[i] if binary[i] else '-' for i in range(4)])
            infomap[key].append(int(inf[4]))
    for k in infomap.keys():
        infomap[k].sort()
    
    answer = []
    for q in query:
        a, _, b, _, c, _, d, score = q.split()
        key = ''.join([a, b, c, d])
        idx = bisect.bisect_left(infomap[key], int(score))
        answer.append(len(infomap[key]) - idx)
        
    return answer

 

총평

 

정확도는 다 맞춰도 효율성이 도저히 통과되지 않았다.

그래서 그냥 '질문하기'에 있는 풀이를 참고하였다. 이 풀이를 온전히 내 것을 만들려면 시간이 좀 걸릴 것 같다.