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

요약

2021 KAKAO BLIND RECRUITMENT 문제.

지원자가 속할 수 있는 그룹을 모두 만들고, 점수만 리스트에 저장해야 한다.

Binary search를 할 때 주의점. 찾고자 하는 리스트에 같은 중복된 값이 있을 때 어떻게 처리해야 할까?

이걸 간과하고 있다가 시간을 많이 썼다...

이 문제에서는 그냥 더 작은 인덱스로 이동하게끔 처리한다.

코드

def binary_search(group, target):
    n = len(group)
    left, right = 0, n-1
    while left <= right:
        mid = (left+right)//2
        if group[mid] < target:
            left = mid+1
        else:
            right = mid-1
    return n - left

def solution(info, query):
    
    answer = []

    group = dict()
    null = '-'
    
    for lang in ("cpp", "java", "python", null):
        for field in ("backend", "frontend", null):
            for career in ("junior", "senior", null):
                for food in ("chicken", "pizza", null):
                    group[lang+field+career+food] = list()
    
    for applicant in info:
        lang, field, career, food, score = applicant.split()
        for l in (lang, null):
            for f in (field, null):
                for c in (career, null):
                    for d in (food, null):
                        group[l+f+c+d].append(int(score))
                        
    [group[key].sort() for key in group]
    
    for q in query:
        lang, field, career, food, score = q.replace("and", '').split()
        count = binary_search(group[lang+field+career+food], int(score))
        answer.append(count)
    
    return answer