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

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

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

---

📍 Problem

지원자 정보가 list로 들어오고, 각 지원자의 정보는 조건  '개발언어, 직군, 경력, 소울 푸드'  4가지와 코딩 테스트 점수로 구성된다. 지원자중 조건 을 만족하면서 코딩테스트 점수를 X점 이상 받은 사람 수를 구한다.

info	query	result
["java backend junior pizza 150",  "python frontend senior chicken 210",  "python frontend senior chicken 150",  "cpp backend senior pizza 260",  "java backend junior chicken 80",  "python backend senior chicken 50"]	["java and backend and junior and pizza 100",  "python and frontend and senior and chicken 200",  "cpp and - and senior and pizza 250",  "- and backend and senior and - 150",  "- and - and - and chicken 100","- and - and - and - 150"]	[1,1,1,1,2,4]

쿼리의 '-' 표시는 해당 조건을 고려하지 않는다는 의미이다. 

---

💡 Solution

경우의 수와 조건 파싱을 신경써주면 되는 문제이다. 

각 지원자의 정보가 해당할 수 있는 모든 쿼리를 비트 마스크로 미리 구성한다. 

 

예를 들어, "java backend junior pizza 150" 정보의 지원자는

"- and - and - and -", "java and - and - and -", "- and backend and - and -" .... "java and backend and junior and pizza"

-> 총 2**4 = 16개의 조건에 만족될 수 있다.

 

이 때, 만들어진 쿼리에 X 점수의 지원자가 한명 존재한다는 의미로 쿼리에 해당 지원자의 점수를 저장한다. 따라서 지원자는 총 16가지 key에 점수가 저장된다. (key 구성은 조건을 구별할 수 있도록 구성하면 된다.)

-> ex. combination_dict["java backend junior pizza"] = [150]

 

그리고 쿼리가 들어오면, combination_dict에서 쿼리에 해당하는 조건을 찾아서 점수를 만족하면 count 해주면 된다. 

from collections import defaultdict

def solution(info, query):
    answer = []
    combination_dict = defaultdict(list)
    for i in info:
        data = i.split()
        for b in range(1 << 4):
            comb = ""
            for j in range(4):
                if b & (1 << j) > 0:
                    comb += data[j]
                else:
                    comb += "-"
            combination_dict[comb].append(int(data[4]))

    for q in query:
        q_list = q.split()
        q_list = [x for x in q_list if x != 'and']
        score = q_list.pop()
        q_str = ''.join(q_list)

        cnt = len([x for x in combination_dict[q_str] if x >= int(score)])
        answer.append(cnt)

    return answer

위 코드는 간단하지만 실행 결과 정확성 테스트는 통과하지만 효율성 테스트에서 실패한다. 

이 문제는 python에서 효율성 테스트를 통과하려면 점수를 만족하는 지원자를 찾을때 그냥 for문 비교가 아닌 이진 탐색으로 찾아야한다. 점수 리스트에서 특정 점수 이상의 값을 찾기 위해 하나씩 비교하면 데이터가 많을 수록 cost가 커지기 때문이다.

 

이진 탐색은 직접 구현하거나 bisect 라이브러리를 사용할 수 있다. 

1. 구현

from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    answer = []
    combination_dict = defaultdict(list)
    for i in info:
        data = i.split()
        for b in range(1 << 4):
            comb = ""
            for j in range(4):
                if b & (1 << j) > 0:
                    comb += data[j]
                else:
                    comb += "-"
            combination_dict[comb].append(int(data[4]))

    for scores in combination_dict.values():
        scores.sort()
        
    for q in query:
        q_list = q.split()
        q_list = [x for x in q_list if x != 'and']
        score = q_list.pop()
        q_str = ''.join(q_list)
        
        # score보다 큰 element 탐색
        points = combination_dict[q_str]
        
        # 이진탐색 2.구현
        left = 0
        right = len(points)
        while left < right:
            mid = (left + right) // 2
            if points[mid] >= int(score):
                right = mid
            else:
                left = mid + 1

        answer.append(len(points) - left)

    return answer

2. 라이브러리 이용

from collections import defaultdict
from bisect import bisect_left

def solution(info, query):
    answer = []
    combination_dict = defaultdict(list)
    for i in info:
        data = i.split()
        for b in range(1 << 4):
            comb = ""
            for j in range(4):
                if b & (1 << j) > 0:
                    comb += data[j]
                else:
                    comb += "-"
            combination_dict[comb].append(int(data[4]))

    for scores in combination_dict.values():
        scores.sort()
        
    for q in query:
        q_list = q.split()
        q_list = [x for x in q_list if x != 'and']
        score = q_list.pop()
        q_str = ''.join(q_list)
        
        # score보다 큰 element 탐색
        points = combination_dict[q_str]
        
        # 이진 탐색 2. bisect 라이브러리
        left = bisect_left(points, int(score))

        answer.append(len(points) - left)

    return answer