[프로그래머스] / [Level 2] / [Python] 순위 검색

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

프로그래머스

---

단순히 2중 for문을 사용해서 하나씩 탐색하는 코드로는 효율성 테스트를 해결할 수 없었다.

 

다른 사람의 풀이를 참고했고, 해결 방법으로는 Dictonary를 만들어 경우의 수를 담고

정렬된 데이터에서 빠른 검색이 가능한 이진 탐색(Binary Search)를 통해 결과값을 얻습니다.

 

Lower Bound 이진 탐색으로 구현

from itertools import combinations
def solution(info, query):
    answer = []
    DB = {}
    
    for i in info:
        info_ = i.split()
        score = int(info_[-1])
        conditions = info_[:-1]
        
        for n in range(5):
            c = list(combinations(range(4), n))
            for c_ in c:
                conditions_ = conditions.copy()
                for v in c_:
                    conditions_[v] = '-'
                conditions_ = ''.join(conditions_)
                if conditions_ in DB:
                    DB[conditions_].append(score)
                else:
                    DB[conditions_] = [score]
                    
    for v in DB.values():
        v.sort()

    for q in query:
        q = q.replace("and ", "").split()
        DB_key = ''.join(q[:-1])
        DB_score = int(q[-1])

        if DB_key in DB:
            data = DB[DB_key]
            if len(data) > 0:
                start, end = 0, len(data)
                while start != end and start != len(data):
                    if data[(start + end) // 2] >= DB_score:
                        end = (start + end) // 2
                    else:
                        start = (start + end) // 2 + 1
                answer.append(len(data) - start)
        else:
            answer.append(0)
        
    return answer

 

이진 탐색 라이브러리 (bisect) 사용

from itertools import combinations
from bisect import bisect_left
def solution(info, query):
    answer = [0 for _ in range(len(query))]
    info_list = list()
    query_list = list()
        
    for idx, (i, q) in enumerate(zip(info, query)):
        info_list.append(i.split())
        query_list.append(q.replace('and', '').split())

    for idx, query in enumerate(query_list):
        for info in info_list:
            if int(query[4]) <= int(info[4]):
                for i in range(4):
                    if query[i] == "-":
                        continue
                    elif query[i] != info[i]:
                        break
                else:
                    answer[idx] += 1
    return answer