[프로그래머스 Level2] 순위 검색 - 파이썬(Python) - 2021 KAKAO BLIND RECRUITMENT

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

프로그래머스

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

• 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
• 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
• 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
• 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

• 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
• 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?

 

---

시간초과를 조심해야하는 문제였다.

각 항목 별로 나올 수 있는 케이스는 (3가지, 2가지, 2가지, 2가지, 점수)이므로 '-'의 경우도 생각해주기 위해 4중 for문을 사용하여 나올 수 있는 모든 케이스들를 딕셔너리의 키로 넣었다. 초기화 이후에는 info 리스트에서 info를 하나씩 꺼내서 만들어질 수 있는 케이스들에 각각의 점수들의 리스트를 딕셔너리의 값으로 넣었다.

# 모든 케이스들 초기화
cases = {}
for lan in ['cpp', 'java', 'python', '-']:
    for job in ['backend', 'frontend', '-']:
        for career in ['junior', 'senior', '-']:
            for food in ['chicken', 'pizza', '-']:
                cases[lan+' '+job+' '+career+' '+food] = []

# info로 가능한 케이스들에 점수 추가
for info in infos:
    info = info.split()
    for lan in [info[0], '-']:
        for job in [info[1], '-']:
            for career in [info[2], '-']:
                for food in [info[3], '-']:
                    cases[lan+' '+job+' '+career+' '+food].append(int(info[4]))

 

이후에는 이제 query에서 하나씩 꺼내어 그 케이스에 존재하는 점수들을 확인한다. 코딩테스트 점수가 query에 제시된 점수 이상의 점수이어야하므로 점수를 통과할 수 있는 인덱스를 이진 탐색을 통해 뽑아낸다. 이 때의 이진 탐색을 위에 query 순회에 앞서 모든 케이스 딕셔너리의 값들을 오름차순 정렬해두어야 한다. 

# 쿼리에서 나오는 케이스들에 가능한 갯수 구하기
for query in queries:
    query = query.split(' and ')
    query[3], score = query[3].split()
    scores = cases[query[0]+' '+query[1]+' '+query[2]+' '+query[3]]
    answer.append(len(scores)-binary_search(scores, 0, len(scores), int(score)))
return answer

 

이 과정에서 계속 오류가 났는데, 오늘 처음으로 이진탐색에는 상한선, 하한선(upper bound, lower bound)를 구하기 위한 탐색 구현이 target의 값을 찾는 것과는 조금 다르다는 것을 알게 되었다.

이 문제에서는 리스트에서 값의 하한선을 구하는 탐색 알고리즘을 사용하였다.

def binary_search(arr, start, end, target):
    while start < end:
        mid = start + (end - start) // 2
        if arr[mid] >= target:
            end = mid
        else:
            start = mid + 1
    return start

 

 

<< 전체 코드 >>

def binary_search(arr, start, end, target): # lower_bound
    while start < end:
        mid = start + (end - start) // 2
        if arr[mid] >= target:
            end = mid
        else:
            start = mid + 1
    return start
    
def solution(infos, queries):
    answer = []
    # 모든 케이스들 초기화
    cases = {}
    for lan in ['cpp', 'java', 'python', '-']:
        for job in ['backend', 'frontend', '-']:
            for career in ['junior', 'senior', '-']:
                for food in ['chicken', 'pizza', '-']:
                    cases[lan+' '+job+' '+career+' '+food] = []
                    
    # info로 가능한 케이스들에 점수 추가
    for info in infos:
        info = info.split()
        for lan in [info[0], '-']:
            for job in [info[1], '-']:
                for career in [info[2], '-']:
                    for food in [info[3], '-']:
                        cases[lan+' '+job+' '+career+' '+food].append(int(info[4]))
    
    # 각 케이스 별 점수 오름차순 정리
    for k in cases.keys():
        cases[k].sort()
        
    # 쿼리에서 나오는 케이스들에 가능한 갯수 구하기
    for query in queries:
        query = query.split(' and ')
        query[3], score = query[3].split()
        scores = cases[query[0]+' '+query[1]+' '+query[2]+' '+query[3]]
        answer.append(len(scores)-binary_search(scores, 0, len(scores), int(score)))
    return answer