[Level 2] 순위 검색

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

코딩테스트 연습 - 순위 검색

---

접근

다른 사람들의 풀이를 참고하였다.

먼저 한 지원자가 python backend, junior, pizza 150일 때 - backend junior pizza 150을 검색할 때도 뽑힐 수 있어야하고 - - - pizza 100일 때도 뽑힐 수 있어야한다. 따라서 지원자들의 조건으로 검색될 수 있는 모든 조합을 만들어 키 값으로 딕셔너리에 저장한다. 즉 python backend junior pizza를 키 값으로 딕셔너리에 저장하고 - - - pizza를 키 값으로 저장하는 것이다. 값은 150이 된다.

이후에 query 내의 조건들을 탐색하여 딕셔너리에 저장된 키의 형태로 만들어주고 키에 해당되는 배열 내에서 특정 점수 이상인 인덱스를 이진 탐색으로 찾아준다.

 

구현

- 지원자들의 상태를 통해 만들 수 있는 모든 검색 조건을 만들어준다.

- '-'는 0~3의 인덱스에 들어갈 수 있기 때문에 range(4)에서 조합을 k개를 선택하는 조합을 만들어낸다.

- 만들어진 조합을 통해 해당 인덱스에 '-'를 대입하여 key를 생성하고

- 해당 key에 score를 리스트 내에 저장한다.

    table = dict()
    for info in info_list:
        data = info.split(' ')[:4]
        score = int(info.split(' ')[-1])
        key = ''.join(data)
        if key in table:
            table[key].append(score)
        else:
            table[key] = [score]

        for k in range(1, 5):
            index_list = list(combinations(range(4), k))
            for index in index_list:
                temp = info.split(' ')[:4]
                for i in index:
                    temp[i] = '-'
                key = ''.join(temp)
                if key in table:
                    table[key].append(score)
                else:
                    table[key] = [score, ]

- 이제 딕셔너리 table 내의 리스트들으 모두 오름차순으로 정렬한다.

- 그리고 검색할 조건들을 위에서 만든 key 형태로 만들어준다.

- 만들어진 key가 table에 존재한다면 이진 탐색을 통해 score 이상이 처음 시작되는 인덱스를 반환하도록 한다.

- 만약 그러한 인덱스가 존재하지 않는다면 0을 최종해에 대입한다.

- 또한 탐색을 할 key가 table내에 존재하지 않아도 0을 최종해에 대입한다.

for value in table.values():
        value.sort()
        
    for q in query:
        q = [i for i in q.split() if i != 'and']
        cmd = ''.join(q[:-1])
        score = int(q[-1])
        
        if cmd in table:
            numbers = table[cmd]
            N = len(numbers)

            idx = binary_search(0, N-1, score, numbers)
            if(numbers[idx] >= score):
                answer.append(N - idx)
            else:
                answer.append(0)
        else:
            answer.append(0)

---

전체 코드

from itertools import combinations

def binary_search(left, right, target, numbers):
    while left < right:
        mid = (left + right) // 2
        if numbers[mid] < target:
            left = mid + 1
        else:
            right = mid
    return right

def solution(info_list, query):
    answer = []
    table = dict()
    for info in info_list:
        data = info.split(' ')[:4]
        score = int(info.split(' ')[-1])
        key = ''.join(data)
        if key in table:
            table[key].append(score)
        else:
            table[key] = [score]

        for k in range(1, 5):
            index_list = list(combinations(range(4), k))
            for index in index_list:
                temp = info.split(' ')[:4]
                for i in index:
                    temp[i] = '-'
                key = ''.join(temp)
                if key in table:
                    table[key].append(score)
                else:
                    table[key] = [score, ]
    
    for value in table.values():
        value.sort()
        
    for q in query:
        q = [i for i in q.split() if i != 'and']
        cmd = ''.join(q[:-1])
        score = int(q[-1])
        
        if cmd in table:
            numbers = table[cmd]
            N = len(numbers)

            idx = binary_search(0, N-1, score, numbers)
            if(numbers[idx] >= score):
                answer.append(N - idx)
            else:
                answer.append(0)
        else:
            answer.append(0)

    return answer