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

Programmers, 순위 검색

2021 KAKAO BLIND RECRUITMENT(2021년 카카오 공개 채용)

TL;DR

• 구현(implementation)
• 이진 탐색(Binary search)

문제 요약

1. info에 지원자가 작성한 4가지 정보와 코딩 테스트 정보가 문자열로 구성된 배열이 주어진다.
2. query에 개발팀에서 궁금해하는 문의 조건이 문자열로 구성된 배열이 주어진다.
3. 개발팀이 궁금해하는 조건에 맞는 지원자의 수를 배열에 담아 반환하는 함수를 작성한다.
4. 개발팀이 궁금해하는 조건에서 '-'는 해당 조건을 고려하지 않는다는 뜻이다. 
5. 문제의 경우 정확성과 효율성 평가가 포함되어 있다.

 

- 지원자들이 작성한 조건과 코딩 테스트에서 개발팀이 원하는 조건에 해당하는 사람이 몇 명인지 반환하는 함수를 작성하면 되는 문제이다.

- 상관없음 조건('-')가 있다는 점에 유의해서 구현을 해야 한다. 이는 입출력 예시에서 살펴볼 수 있다.

- 보통 효율성 검사가 포함된 경우에는 입력의 크기가 커 완전 탐색(Brute force)로 문제를 해결할 수 없는 경우라고 생각하면 된다. 따라서 문제를 해결할 때 단순 완전 탐색이 아닌 시간 복잡도가 크지 않도록 코드를 작성해야 할 필요가 있다.

입출력 형태

입출력 예시

 

query를 살펴보면 각 조건은 다음과 같다.

1. java로 코테를 봤으며, backend 직군을 선택했고, junior 경력이면서, pizza가 소울푸드이고 코딩 테스트 점수가 100점 이상인 사람
2. python로 코테를 봤으며, frontend 직군을 선택했고, senior 경력이면서, chicken이 소울푸드이고 코딩 테스트 점수가 200점 이상인 사람
3. cpp로 코테를 봤으며, 직군은 상관없고, senior 경력이면서, pizza가 소울푸드이고 코딩 테스트 점수가 250점 이상인 사람
4. 코테를 본 언어가 상관없고, backend 직군을 선택했고, senior 경력이면서, 소울푸드가 상관없고 코딩 테스트 점수가 150점 이상인 사람
5. 코테를 본 언어가 상관없고, 직군도 상관없고, 경력도 상관없고, chicken이 소울푸드이고 코딩 테스트 점수가 100점 이상인 사람
6. 모든 조건이 상관없으면서 코딩 테스트 점수가 150점 이상인 사람

조건에 '-'가 포함되어 있다면 해당 조건은 "어떤 조건이여도 상관없다."는 뜻으로 해석할 수 있다. 이를 잘 활용해서 문제를 해결해야 한다. 그 외에는 주어진 지원자들의 내역 중 조건에 맞는 사람들을 찾아서 문제를 해결하면 된다.

풀이

'-'는 모든 조건을 만족한다는 것으로 이를 포함시켜 조건을 조회할 경우 높은 시간 복잡도를 갖게 된다. 따라서 이를 효율적으로 할 수 있는 방법을 사용해야 한다. 여러 방법이 존재하겠지만, 다음의 성질을 이용하면 보다 낮은 시간 복잡도로 문제를 해결할 수 있다.

java backend junior pizza를 조건으로 갖고 있는 사람의 경우
"java backend junior pizza", "- backend junior, pizza", "java - junior, pizza", "java backend - pizza", "java backend junior -", "- - junior pizza", "- backend - pizza", "- backend junior -", "java - - pizza", "java - junior -", "java backend - -", "- - - pizza", "- - junior -", "- backend - -", "java - - -", "- - - -" 총 16개의 조건에 해당하는 사람이라고 말할 수 있다.

 

지원자들의 조건으로 만들 수 있는 모든 경우의 수를 key, 해당 지원자의 코딩 테스트 점수를 value로 하는 딕셔너리를 구성하면 조회에 필요한 시간 복잡도를 풀일 수 있다.

from collections import defaultdict
from itertools import combinations
def solution(info, query):
    answer = []
    # 지원자가 속할 수 있는 모든 조건을 key로, 해당 조건에 속하는 지원자들의 점수들을 value로
    # key에 대해서 점수를 만족하는 지원자를 저장
    infos = defaultdict(list)
    for i in info:
        conditions = i.split()[:-1]
        score = int(i.split()[-1])
        for r in range(5):
            combis = list(combinations(range(4), r)) # '-'로 바꿀 경우의 수를 추출

            for c in combis: # 각 경우에 수에 대해 '-'로 바꾼 조건을 생성
                test_cases = conditions[:]
                for v in c:
                    test_cases[v] = '-'
                infos['_'.join(test_cases)].append(score)
    for item in infos:
        infos[item].sort()
    
    for q in query:
        q = q.replace('and', '').split()
        conditions = '_'.join(q[:-1])
        score = int(q[-1])

        if conditions in list(infos):
            data = infos[conditions]
            if len(data) > 0:
                start, end = 0, len(data)
                while start != end and start != len(data):
                    if data[(start + end) // 2] >= score:
                        end = (start + end) // 2
                    else:
                        start = (start + end) // 2 + 1
                answer.append(len(data) - start)
        else:
            answer.append(0)
    return answer

 

작성한 코드는 위와 같다. 크게 두 가지 부분으로 나눌 수 있다.

첫 번째 부분은 info를 조회해서 지원자들의 정보를 딕셔너리로 구성하는 부분이다.

지원자들의 작성 내역에 해당하는 것을 조건(conditions)와 점수(score)로 나눈다.

- 조건의 경우 해당 조건으로 만들 수 있는 다른 조건들을 모두 만든다. 이 때, python의 itertools.combinations를 사용해서 '-'로 바꿀 경우를 만들어준다. 그리고 동일한 조건을 key로 점수를 value로 한 딕셔너리를 만든다. 이를 통해 query에서 주어진 조건을 key로 조회하면 되기 때문에 시간 복잡도를 O(1)로 줄일 수 있다.

 

두 번째 부분은 개발팀에서 주어진 쿼리를 바탕으로 만족하는 지원자들의 현황을 조회하는 부분이다.

주어진 조건이 딕셔너리에 존재한다면 해당하는 사람들 중 만족하는 점수와 비교를 통해 조건에 해당하는 사람의 수를 알아낸다.

이 때, Binary search를 사용하여 코딩 테스트 점수 조건을 만족하는 사람을 구한다. binary search가 진행되고 나면 start에 최소 score인 인덱스가 저장된다.

 

만족하는 사람의 수를 answer에 저장한다. 만족하는 조건이 없다면 0을 저장한다.