[프로그래머스][구현][조합] 순위 검색

순위 검색

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

프로그래머스

 

 

• 내 풀이 - 시간초과 fail
  
  • 2중 for문으로 query 100,000 * 최대 인원 50,000 해서 터짐
  • 그 뿐만 아니라, 교집합 자체가 O(N) → 교집합 과정만 O(50,000)

from collections import defaultdict

def solution(info, query):
    answer = []
    dic=defaultdict(list)
    dic['-']=[i for i in range(len(info))]
    for idx, info_val in enumerate(info):
        for idx2, val in enumerate(list(info_val.split())):
            if idx2==4:
                dic[idx].append(val)
                continue
            dic[val].append(idx)
    
    for qr in query:
        lang,job,exp,foodscore=qr.split(' and ')
        food,score=foodscore.split()

        tmp_idx=set(dic[lang]) & set(dic[job]) & set(dic[exp]) & set(dic[food])
        cnt=0
        for idx in tmp_idx:
            if int(dic[idx][0])>=int(score):
                cnt+=1
        answer.append(cnt)

    return answer

 

 

• 다른 사람 풀이
  • info 하나마다 16가지 경우의 수가 나옴 → 16 *50000
    • 조건을 모두 담은 튜플로 만든 key에 점수를 value로 가지는 딕셔너리 생성
  • query 돌면서 해당 조건들을 tuple로 감싸서 key검색
    • set 아님 주의
  • 이분탐색 bisect_left로 score 값 위치(idx) 찾기
    • 길이 - idx = score보다 큰 값의 갯수

from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    answer = []
    dic=defaultdict(list)
    for i in info:
        i = i.split()
        for a in [i[0], '-']:
            for b in [i[1], '-']:
                for c in [i[2], '-']:
                    for d in [i[3], '-']:
                        dic[(a, b, c, d)].append(int(i[4]))

    # 지원자 점수 오름차순 정렬
    for k in dic:
        dic[k].sort()

    for qr in query:
        qr = qr.replace("and ", "")
        qr = qr.split()
        
        target_key = tuple(qr[:-1])
        target_score = int(qr[-1])
        
        cnt = 0
        target_list = dic[target_key]
        idx = bisect_left(target_list, target_score)
        cnt = len(target_list) - idx
        answer.append(cnt)      

    return answer