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

lower bound의 존재를 몰라서, 결국 카카오 풀이를 참고한 문제.
lower bound의 개념을 살펴봤지만, 아직 어렵다.

카카오 풀이(https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/)에서
문제 접근 방법을 이해하기 쉽게 설명했다. 여기서 아이디어를 얻고, 코드로 구현하면 된다.

핵심은 문의조건의 -을 처리하기위해, info[i]에서 점수와 4가지 항목(언어, 직군, 경력, 소울푸드)을 분리한다. 이후 4가지 항목에 대하여, -가 있을 때와 없을 때를 고려하여, 지원서를 재정의하고 이를 딕셔너리의 key로 정한다. 그리고 value는 정수형의 코딩테스트 점수을 담는 리스트로 정한다.(i.e. info[i]에 대해, 나올 수 있는 경우의 수는 16가지)

이미 존재하는 key라면, value의 자료형이 list이기 때문에 코딩테스트 점수를 그대로 추가해주면 된다.

이에 대한 예시는 카카오 해설에 있다.

그리고 각 쿼리에 대해, 해당 쿼리를 딕셔너리의 key형식에 맞게 파싱하고, 딕셔너리의 key값이 될 수 있으면, 쿼리에 있는 코딩테스트 점수와 딕셔너리의 value에 있는 코딩테스트 점수들과 비교해서, 쿼리에 있는 코딩테스트보다 크거나 같은 값이 몇 개 있는지 반환하면 된다.
이를 위해 lower bound 사용해야하고 파이썬은 관련된 표준 라이브러리, bisect를 지원한다.

bisect 라이브러리 참고 링크(https://docs.python.org/ko/3/library/bisect.html)

key, value 형식 예제(딕셔너리로 지원서 재정의)

내가 정의한 key-value형식
문제에서 info[0] = "java backend junior pizza 150"이므로,
info_dict = {}

info_dict["javabackendjuniorpizza"] = [150]
info_dict["-backendjuniorpizza"] = [150]
info_dict["java-juniorpizza"] = [150]
info_dict["javabackend-pizza"] = [150]

info_dict["javabackendjunior-"] = [150]
info_dict["--juniorpizza"] = [150]
info_dict["-backend-pizza"] = [150]
info_dict["-backendjunior-"] = [150]

info_dict["java--pizza"] = [150]
info_dict["java-junior-"] = [150]
info_dict["javabackend--"] = [150]
info_dict["---pizza"] = [150]

info_dict["--junior-"] = [150]
info_dict["-backend--"] = [150]
info_dict["java---"] = [150]
info_dict["----"] = [150]

따라서, 16가지의 경우의수가 나온다.

info의 모든 원소에 대해, 위처럼 만들어준다. 만약 key가 이미 존재하면, value가 list이기 때문에, 아래처럼 그대로 추가해주면된다.

info_dict["----"] = [150, 210]

한편, query의 원소는 info_dict의 key, value 형식에 맞게 처리한다.

문제에서 query[0] = "java and backend and junior and pizza 100"이므로
점수와 문의조건을 분리하고 처리한다. 따라서 결과는 아래와 같다.
_q = 'javabackendjuniorpizza', score = int(100)

이후 _q를 info_dict의 key로 접근하고, 만약 key가 존재하면, score값과 같거나 큰 점수들을 value에서 찾으면 된다.

코드

import bisect

changes = []
tmp = []

# 16가지의 경우의 수를 만들어주는 함수
def make_cases():
    global changes, tmp
    if len(tmp) == 4:
        t = []
        for index in tmp: t.append(index)
        changes.append(t)
        return
    
    for i in (False, True):
        tmp.append(i)
        make_cases()
        tmp.pop()

# True를 가리키는 인덱스에 해당하는 속성 값을 '-'으로 바꿔준다.
def replace(change, data):
    for i in range(4):
        if change[i]: data[i] = '-'

    return data

def copy(data):
    _data = []
    for item in data: _data.append(item)

    return _data

def search(scores, num):
    size = len(scores)
    return size - bisect.bisect_left(scores, num, lo=0, hi=size)

def solution(info, query):
    global changes
    answer = []
    info_dict = {}
    make_cases()

    # query를 위한 info 전처리
    for data in info:
        data = data.split()
        score = int(data[-1])
        data = data[:4]
        
        for change in changes:
            _data = copy(data)
            _data = replace(change, _data)
            _data = ''.join(_data)

            if _data not in info_dict.keys(): info_dict[_data] = [score]
            else: info_dict[_data].append(score)
    
    # info_dict[key] 정렬
    for key in info_dict.keys(): info_dict[key].sort()
    
    for q in query:
        q = q.split()
        score = int(q[-1])
        _q = ''
        
        # query 문자열 처리
        for item in q[:len(q)-1]:
            if item != 'and': _q += item
                
        # 문의 조건을 만족하는 지원서들의 수 찾기
        if _q not in info_dict.keys(): answer.append(0)
        else:
            cnt = search(info_dict[_q], score)
            answer.append(cnt)

    return answer