2021 KAKAO BLIND RECRUITMENT 순위 검색 (python)

def solution(info, query):
    infoMap = {}
    for f in info:
        tempMap = infoMap
        infos = f.split(' ')
        for i in range(4):
            if infos[i] not in tempMap:
                tempMap[infos[i]] = {}
            tempMap = tempMap[infos[i]]
        
        if 'score' not in tempMap:
            tempMap['score'] = []
        tempMap['score'].append(int(infos[4]))
        tempMap['score'].sort()
    
    answer = []
    
    for q in query:
        condition = q.split(' and ')
        score = int(condition[3].split(' ')[1])
        condition[3] = condition[3].split(' ')[0]
        
        answer.append(dfs(condition, 0, infoMap, score))
        
    return answer

def dfs(condition, depth, tempMap, score):
    if depth == 4:
        return findNum(tempMap['score'], score)
    
    if condition[depth] == '-':
        values = tempMap.keys()
        
        ret = 0
        for val in values:
            ret += dfs(condition, depth+1, tempMap[val], score)
        return ret
        
    if condition[depth] not in tempMap:
        return 0

    return dfs(condition, depth+1, tempMap[condition[depth]], score)

def findNum(scores, score):
    low = 0
    high = len(scores)
    
    while low < high:
        mid = (low + high) // 2
        if scores[mid] >= score:
            high = mid
        else:
            low = mid + 1
    
    return len(scores) - high

 

trie와 비슷한 방식으로 구현하였는데 특정 조건들 마다 딕셔너리를 타고 들어가 마지막 조건에서 같은 조건들의 점수들을 'score'를 key로 갖는 list에 저장하여 lowerBound로 찾기 위하여 정렬하였다. query에 '-'가 들어가는 경우는 재귀 형태로 두 가지 경우를 모두 계산하고 조건을 만족하는 지원자의 수를 모두 더하여 리턴하는 함수를 만들었다.