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

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

프로그래머스

🤔 문제분석

📝 문제요약

쿼리가 주어지는데 해당 쿼리에 따라서 몇명이 선택되는지 계산하는 문제이다.

개발언어, 직군 항목, 경력구분, 선호하는 소울푸드, 코딩테스트 점수가 쿼리로 주어지고 해당 쿼리에 따라서 몇명이 존재하는지 파악하여 리턴하면 된다.

🎯 필요한 개념

• 트라이노드 : 각각의 문자열에 따라서 자식 노드를 만들고 자식노드의 리프노드가 코딩테스트 점수의 리스트를 가지고 있으면 된다.
• 이분탐색 : 코딩테스틔 점수 리스트는 처음 초기화 할때 정렬된 데이터로 초기화 해둔뒤, 쿼리가 일어날때 주어진 스코어보다 큰 개수를 찾아야함으로, 이분탐색으로 빠르게 찾는다.

✅ 알고리즘

1. 트라이노드로 노드들을 초기화 한다.
2. search 함수로 스코어보다 큰 개수를 리턴해야하는데, search 함수는 주어진 쿼리의 모든 노드를 체크한다.

💻 코드

# <https://school.programmers.co.kr/learn/courses/30/lessons/72412>
def solution(info, query):
    def bisect_left(arr, score):
        start = 0
        end = len(arr)
        
        while start < end:
            mid = (start + end) // 2
            if arr[mid] < score:
                start = mid + 1
            else:
                end = mid

        return start
    
    class Node():
        def __init__(self) -> None:
            self.child = {}
            self.data = []
        
    class Trie():
        def __init__(self) -> None:
            self.head = Node()
            
        def insert(self, info):
            current_node = self.head
            n = len(info)
            for i in range(n-1):
                if info[i] not in current_node.child:
                    current_node.child[info[i]] = Node()
                
                current_node = current_node.child[info[i]]
            
            scores = current_node.data
            score = int(info[-1])
            idx = bisect_left(scores, score)
            scores.insert(idx, score)
            
        
        def search(self, query):
            current_node = [self.head]
            n = len(query)
            
            for i in range(n-1):
                next_current_node = []
                # '-'가 등장할 경우 모든 child들을 다음 검색할 노드에 넣는다.
                if query[i] == '-':
                    for node in current_node:
                        for key in node.child.keys():
                            next_current_node.append(node.child[key])
                else:
                    for node in current_node:
                        # query[i]에 존재하는 노드만 추가한다.
                        if query[i] in node.child:
                            next_current_node.append(node.child[query[i]])
                
                current_node = next_current_node
            
            cnt = 0
            score = int(query[-1])
            # 마지막 노드를 순회하면서 score보다 큰 값을 찾는다.
            for node in current_node:
                scores = node.data
                n = len(scores)
                l = bisect_left(scores, score)
                cnt += n - l
                
            return cnt
                    
    trie = Trie()
    for i in info:
        i = i.split(' ')
        trie.insert(i)
    
    answer = []
    for q in query:
        q = q.replace(" and", "").split(' ')
        answer.append(trie.search(q))
        
    return answer