[프로그래머스] 순위 검색 / KAKAO BLIND RECRUITMENT / 파이썬

문제

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

풀이

1. 가능한 개발 언어, 지원직군, 경력구분, 소울푸드를 딕셔너리에 모든 경우의 수를 key로 잡습니다.

❗️조건을 고려하지 않는 경우도 있으니 없는 경우도 넣어줍니다.

 

2. 모든 경우의 수가 담긴 딕셔너리에 지원자의 개발 언어, 지원 직군, 경력 구분, 소울 푸드가 포함 될 수 있는 키가 있다면 해당 키에 코딩테스트 점수를 리스트에 추가합니다.

❗️만약 지원자의 리스트가 ["java backend junior pizza"]라면  4가지 항목을 딕셔너리에 들어갈 수 있는 경우의 수를 또 다시 만든 뒤 그 경우의 수 키에 점수를 추가합니다. 

 

3. 딕셔너리의 키에 들어있는 밸류 리스트를 int형으로 매핑해준 후 이진 탐색을 위해 정렬을 해줍니다.

 

4. 쿼리(=문의 조건)을 원하는 지원서의 조건과 원하는 코딩테스트 점수로 나눠줍니다.

❗️지원서의 조건은 딕셔너리의 키와 매칭할 것이고 원하는 코테 점수는 원하는 코테 점수보다 높은  매칭되는 키의 밸류 리스트(=지원자의 점수)들을 필터링할 것 입니다.

 

5. 지원서의 조건과 매칭되는 딕셔너리 키의 밸류(=지원자의 점수 리스트)를 가지고 원하는 코딩테스트보다 같거나 높은 점수를 얻은 사람들만 찾습니다.

❗️효율성을 만족하기 위해 이진탐색으로 조건에 만족하는 코테 점수를 가진 지원자의 수를 찾습니다.

 

코드

from itertools import combinations

# 모든 문의 조건 경우의 수를 딕셔너리 키로 만들고 리턴
def make_combi():
    info_dict = dict()
    lang = ["", "cpp", "java", "python"]
    group = ["", "backend","frontend"]
    career = ["", "junior", "senior"]
    food = ["", "chicken","pizza"]
    
    for l in lang:
        for g in group:
            for c in career:
                for f in food:
                    a = [x for x in [l,g,c,f] if x !=""]
                    info_dict[" ".join(a)]= []
                    
    return info_dict

def solution(info, query):
    answer = []
    info_dict = make_combi()
    
    """
    모든 경우의 수가 담긴 딕셔너리에 지원자의 개발 언어, 지원 직군, 경력 구분, 소울 푸드가 
    포함 될 수 있는 키가 있다면 해당 키에 코딩테스트 점수를 리스트에 추가
    """
    for i in info:
        """
        info 파싱
        "java backend junior pizza 150" 를
        ["java", "backend", "junior", "pizza", "150"]로 파싱
        """
        l = i.split(" ")
        _info , score = l[:4], l[-1]
        for n in range(5):
            for comb in list(combinations(_info,n)):
                info_dict[" ".join(list(comb))].append(score)
    """
    딕셔너리의 키에 들어있는 밸류 리스트의 원소를 int형으로 매핑해준 후 
    이진 탐색을위해 정렬
    """
    for key in info_dict.keys():
        info_dict[key] = sorted(list(map(int,info_dict[key])))
    
    for q in query:
    	"""
        query 파싱
        "java and backend and junior and pizza 100" 를
        ["java", "backend", "junior", "pizza", "100"]로 파싱
        """
        q = [x for x in q.split(" ") if x != "and" and x!="-"]
        
        """
        쿼리(=문의 조건)을 원하는 지원서의 조건과 원하는 코딩테스트 점수로 나눔
        """
        goal = int(q.pop()) # 원하는 코테 점수
        scores = info_dict[" ".join(q)] # 원하는 지원서의 조건
   		
        """
        이분탐색 구간
        start: 리스트 인덱스의 최소값
        end: 리스트 인덱스의 최대값
        """
        start, end = 0, len(scores)
   
        while start < end :
            mid = (start + end) // 2
            
            if scores[mid] >= goal:
                end = mid
            else:
                start = mid + 1
         
        # 리스트 전체길이를 최대로 만족하는 리스트의 인덱스로 빼주면 해당되는 점수를 가진 사용자의 수
        answer.append(len(scores)-start)
        
    return answer