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

def solution(info, query):
    info =  [i.split() for i in info]
    query = [q.split(' and ') for q in query]
    answer = []
    
    for lang, pos, car, x in query:
        soul, scr = x.split()
        cnt = 0
        for i in info:
            qr = [lang, pos, car, soul]
            if '-' in qr:
                for j in range(4):
                    if qr[j] == '-':
                        qr[j] = i[j]
            if qr == i[:-1] and int(i[-1]) >= int(scr):
                cnt += 1
                
        answer.append(cnt)
    return answer

위와 같이 푼 결과는 시간 초과.. 

문제에 대한 질문들을 참고해서 다시 풀었다.

아래는 set과 교집합을 활용한 문제 풀이다.

 

def solution(info, query):
    info =  [i.split() for i in info]
    query = [q.replace('-','').replace('and ','').split() for q in query]
    answer = []
    
    for q in query:
        cnt = 0
        for i in info:
            if len(set(q[:-1]) & set(i[:-1])) == len(q)-1 and int(i[-1]) >= int(q[-1]):
                cnt += 1
        answer.append(cnt)
        
    return answer

결과를 보니 오히려 시간이 더 오래 걸리는 것 같다.

찾아보니 해시테이블과 이진탐색을 사용해야 한다고 했다. 

첫번째나 두번째 방법은 결국 for문을 두 번 돌림으로써 모든 데이터를 비교하는 방법인데,

query 10만 개당 info 5만 개씩 비교하면 50억번을 비교하게 된다. 그래서 시간초과가 난 것이다!!! 

 

 

한 블로그에서 본 답은 다음과 같다.

이진탐색 라이브러리인 bisect를 사용했다.

> 정답코드

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

def solution(information, queries):
    answer = []
    dic = defaultdict(list)
    for info in information:
        info = info.split()
        condition = info[:-1]  
        score = int(info[-1])
        for i in range(5):
            case = list(combinations([0,1,2,3], i))
            for c in case:
                tmp = condition.copy()
                for idx in c:
                    tmp[idx] = "-"
                key = ''.join(tmp)
                dic[key].append(score) 

    for value in dic.values():
        value.sort()   

    for query in queries:
        query = query.replace("and ", "")
        query = query.split()
        target_key = ''.join(query[:-1])
        target_score = int(query[-1])
        count = 0
        if target_key in dic:
            target_list = dic[target_key]
            idx = bisect_left(target_list, target_score)
            count = len(target_list) - idx
        answer.append(count)      
    return answer