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

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

코딩테스트 연습 - 순위 검색

처음 풀이

def solution(info,query):
    answer =[]
    applicants = [['']*5 for i in range(len(info))]
    for i,v in enumerate(info):
        applicants[i] = v.split()
    for v in query:
        want = v.replace('and','').split()
        suc_candidate = 0
        for candidate in applicants:
            if (candidate[0] == want[0] or want[0]=='-') and (candidate[1] == want[1] or want[1]=='-') and (candidate[2] == want[2] or want[2]=='-') and (candidate[3] == want[3] or want[3]=='-'):
                if  want[4]=='-':
                    suc_candidate+=1
                elif int(candidate[4]) >= int(want[4]):
                    suc_candidate+=1
        answer.append(suc_candidate)
    return answer

처음에 막 손가는대로 풀었을 때 정확성은 모두 맞았지만 효율성에서 모두 시간 초과가 났다.

리스트를 사용하면서 조회할 때 많은 시간이 걸린다고 판단해서

set이나 dict를 사용해서 풀 생각이 들었다.

 

수정된 풀이

from itertools import combinations
from collections import defaultdict
from bisect import bisect_left
def combination_cases(data):
    cases = []
    for i in range(5):
        for com in combinations([0, 1, 2, 3], i):
            case = ''
            for idx in range(4):
                if idx in com:
                    case += data[idx]
                else:
                    case += '-'
            cases.append(case)
    return cases
def solution(info,query):
    answer = []
    dict = defaultdict(list)
    for v in info:
        data = v.split()
        cases = combination_cases(data)
        for case in cases:
            dict[case].append(int(data[-1]))
    for case in dict.keys():
        dict[case].sort()
    for q in query:
        data = q.replace('and','').split()
        case , score =''.join(data[:4]) , int(data[-1])
        answer.append(len(dict[case])-bisect_left(dict[case],score))
    return answer

처음 지원자 데이터가 들어왔을 때 가능한 모든 조합을 dict에 추가해주고 score를 등록해준 다음

score를 정렬해주고 bistect를 통해 조회해서 시간을 단축했다.