[프로그래머스 Lv.2] 순위 검색 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72412 

프로그래머스

풀이

레벨 2 문제라는 레벨 분류가 무색하게 문제 풀이를 위한 방법을 고민하는 게 너무나 어려웠다. 구현 난이도로만 따지면 레벨 2가 맞지만 문제 해결을 위한 방법을 생각해 내는 것 자체가 어려워 체감 난이도가 훅 올라가지 않았나 싶다.

 

처음에는 간단히 생각해서 전체 데이터를 순회하면서 조건에 일치하는 사람들의 수를 카운트하는 방법을 고민했으나, 데이터의 수를 보고 다른 방법을 생각해야 한다고 판단했다. 왜냐하면 단순 조회 시에 지원자의 데이터는 최대 5만 개, 검색 쿼리 데이터의 크기는 최대 10만 개이기 때문에 무려 5만 * 10만 = 50억 개의 데이터를 완전탐색으로 체크해야 하기 때문이다. 그렇기에 다른 방법을 사용해야 한다.

 

어찌 됐든 데이터 전체를 조회해서 조건을 만족하는 수를 세야 하기 때문에 전체를 조회하는 과정이 한 번은 필요하다. 그래서 생각한 방법이 한 번 전체 조회를 할 때 미리 조건에 만족하는 수를 O(1)의 시간복잡도 안에 조회할 수 있는 딕셔너리에 저장해 두는 방법이었다.

다음으로 생각해야 할 것은 그럼 딕셔너리의 key와 value를 무엇으로 할 것인가이다. 이는 간단하게 생각할 수 있는 편인데 우리가 정답을 알기 위해 무엇을 조회해야 하는지만 생각하면 알 수 있기 때문이다. 문제에서 특정 조건을 만족하는 점수가 X점 이상인 사람의 수를 알아내라고 했기에 key는 조회 조건, value는 그 조건에 만족하는 지원자의 점수들이라고 생각하면 된다. value의 점수들을 통해 X점 이상인 사람의 수만 카운트할 수 있기 때문이다. 

추가적으로 고려해야 할 것이 "-"의 사용이었는데, "-"가 있는 경우에는 해당 속성의 값에 상관없이 조회가 되는 것이기 때문에 "-" 역시 조회 조건에 포함해주어야 했다. 그래서 결론적으로는 각 지원자 데이터의 각 속성 별로 해당 속성값, "-"를 조합하여 조회 조건 key를 생성하고 key를 사용해 딕셔너리에 저장하도록 하였다.

마지막으로 조건을 만족하는 지원자들의 점수들을 딕셔너리에서 알아내고, X점 이상인 지원자의 수는 이진 탐색을 통해 low_boundary(X보다 크거나 같은 수가 처음 나타나는 곳의 인덱스)을 알아냄으로써 계산할 수 있다. 

from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    answer = []
    db = defaultdict(list)
    
    for i in info:
        person = i.split()
        lan, job, career, food, score = person # 회원 정보를 속성별로 분리
        
        # "-"를 조회 조건(key)에 포함하도록 해당 속성의 값들과 함께 저장하도록 함
        for l in [lan, '-']:
            for j in [job, '-']:
                for c in [career, '-']:
                    for f in [food, '-']:
                        db[l+j+c+f].append(int(score)) # 조건을 key로, 조건을 만족하는 지원자들의 점수를 value로 저장
    
    for key in db: db[key].sort() # 이진 탐색을 사용하여 low_boundary를 계산하기 위해 오름차순으로 정렬
    
    for q in query: # 각 쿼리별로 조건을 만족하는 지원자 중 특정 점수 이상인 지원자의 수를 카운트 
        ops = q.replace("and ", "").split() # and 제거 후 문자열을 배열로 분리
        score = int(ops.pop()) # 배열의 마지막 위치에 위치한 점수 계산
        key = "".join(ops) # 딕셔너리에서의 조회를 위한 key
        
        answer.append(len(db[key])-bisect_left(db[key], score)) # low_boundary를 계산하는 bisect_left 라이브러리를 사용
        
    return answer