[프로그래머스] 순위검색 (Python 풀이)

Problem Point

처음에 생각했던 방안은 개발언어, 직군, 경력, 소울푸드 순서대로 해당하는 것을 탐색하는 방안으로 생각하였다. 그 후 배열 크기를 보고나서 info 5만 , query 10만 인 것을 보고 전체 시간복잡도가 O(nm)이면 바로 시간초과가 날 것을 예상하였다. 만약 실제로 문제를 풀고 있는 상황이었다면 정확성만 통과 했을 문제이다.
30분 정도 해매고 나서 카카오 풀이를 보고 생각나는 대로 다시 풀어보았다.

카카오 : https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

위의 테이블 처럼 해당 조건에 맞는 모든 그룹에 점수 150점을 넣어두어 나중에 조건이 들어오게 되는 경우에 쿼리 점수보다 높은 점수를 골라내는 작업을 하면 된다.

풀이

카카오 풀이를 보고 나서 그룹을 맺어주는 방식에 대해 생각해보았다. 처음에 만능조건인 - 도 그룹의 key로 넣어야 되나 생각을 하였는데 넣지 않더라도 조합이 순서를 지켜주기 때문에 별도로 넣어두지는 않았다. 풀이에서 알 수 있듯이 info 값을 분리하고 나서 점수를 제외한 조합을 그룹의 key값으로 넣어두었다.
그룹을 연결짓고 나서 해당 그룹에 들어있는 점수를 정렬하기 위해 keys()값을 돌면서 정렬해 주었다.
마지막으로 각 쿼리문마다 쿼리의 중요한 부분을 뽑아오는 부분을 리스트 내포로 가져오게 구현하였고 이분탐색은 bisect 를 이용해서 찾고자 하는 점수보다 높거나 같은 값들을 더하여 answer 리스트에 추가한다.

최종풀이

from collections import defaultdict
from itertools import combinations
import bisect
def solution(info, query):
    answer = []
    group=defaultdict(list)
    for i in info:
        temp=i.split()
        score=int(temp.pop())
        for j in range(0,5):
            for k in combinations(temp,j):
                group["".join(k)].append(score)
    for i in group.keys():
        group[i].sort()
    for i in query:
        temp=i.split(" ")
        search=int(temp.pop())
        temp = [ x for x in temp if x!='and' and x!='-']
        temp = "".join(temp)
        lo=bisect.bisect_left(group[temp],search)
        answer.append(len(group[temp])-lo)
    return answer