[KAKAO 2021][Python] 순위 검색

단순히 조건이 여러개 주어지는 걸 보고 교집합으로 풀려고 했다.

하지만 넓은 범위의 쿼리가 여려개 주어진다면 매번 교집합 연산을 해주어야 한다는 점에서 효율성이 부족했다.

오히려 상태조건이 4 * 3 * 3 * 3 으로 몇개 되지 않았기 때문에 dp로 배열을 만들거나 경우의 수에 따라 최초 배열에 삽입시켜 준 후 정렬하는게 약 3배정도 빨랐다.

조건이 적을 땐 모든 조건에 대해 입력해두는게 후에 쿼리를 수행함에 있어 유리한걸 잊지말자.

쿼리문제. 상태인자별로 미리 정리하자. 검색을 단순화 하자.

 

아래는 교집합 코드 그 아래 상태조사 코드

def solution(info, query):
    answer = []
    lang_set = defaultdict(set)
    job_set = defaultdict(set)
    stat_set = defaultdict(set)
    food_set = defaultdict(set)
    score_set = {}
    for idx, each in enumerate(info):
        lang, job, stat, food, score = each.split()
        lang_set[lang].add(idx)
        job_set[job].add(idx)
        stat_set[stat].add(idx)
        food_set[food].add(idx)
        score_set[idx] = int(score)
    for each in query:
        lang, job, stat, last = each.split(' and ')
        food, score = last.split()
        pivot = set([i for i in range(len(info))])
        if lang != '-':
            pivot &= lang_set[lang]
        if job != '-':
            pivot &= job_set[job]
        if stat != '-':
            pivot &= stat_set[stat]
        if food != '-':
            pivot &= food_set[food]
        tmp = sorted([score_set[idx] for idx in pivot])
        left = bisect_left(tmp, int(score))
        answer.append(len(tmp) - left)
    return answer

 

 

정답코드

from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    score_set = defaultdict(list)
    answer = []    
    for each in info:
        lang, job, stat, food, score = each.split()
        for l in (lang, '-'):
            for j in (job, '-'):
                for s in (stat, '-'):
                    for f in (food, '-'):
                        score_set[(l, j, s, f)] += [int(score)]
        
    for value in score_set.values(): 
        value.sort()
    
    for each in query:
        lang, job, stat, last = each.split(' and ')
        food, score = last.split()
        target_set = score_set[(lang, job, stat, food)]
        index = bisect_left(target_set, int(score))
        answer.append(len(target_set) - index)
        
    return answer