2021 KAKAO BLIND RECRUITMENT 순위 검색 Lv. 2

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72412

파이썬 소스: https://bit.ly/3y0bX2o

 

 문제에 주어지는 2개의 배열 info 와 query의 크기는 각각 50000, 100000 입니다. 지원자가 조건에 해당하는지 확인해야 함으로, 단순하게 1개의 조건 마다, 모든 지원자를 검색해 본다면, 시간 복잡도는 아래와 같아서, 효율성 테스트를 통과하기 어렵습니다.

O(5 * 10 ** 4 * 10 ** 5) = O(5 * 10 ** 9)

시간복잡도가 약 50억 정도로, 10억 보다 크기 때문에, 좀더 시간 복잡도를 줄이는 방법이 필요합니다.

지원서에 입력해야 하는 5가지 개발언어, 직군, 경력, 소울푸드, 코딩 테스트 점수 중에서, 앞에 4가지는 코딩 테스트 점수와 비교하는 방식이 다릅니다. 앞에 4가지는 조건과 일치하거나 해당 조건을 고려하지 않고, 모든 지원자의 숫자를 세는 방식입니다. 마지막 조건인 코딩 테스트만 몇점 이상인 지원자를 세는 방식입니다. 따라서, 앞의 4가지와 코딩 테스트 점수를 따로 나눠서, 보다 빨리 지원자를 검색할 방법을 알아봐야 합니다.

 개발언어, 직군, 경력, 소울푸드, 이 4가지가 가질 수 있는 값의 종류가 많지 않습니다. 개발언어 3가지, 직군 2가지, 경력 2가지, 소울푸드 2가지입니다. 따라서, 일종의 트리형태로 변환한다면, 루트노드는 자식노드로 cpp, java, python 3개의 노드를 가집니다. 3개의 프로그래밍 언어 노드 마다, 2개의 직군 노드(backend, frontend)가 있습니다. 그 다음에는 2개의 경력 노드(junior, senior)가 있구요, 마지막으로 소울 푸드 노드(chicken, pizza)가 있습니다.

 이렇게 트리의 형태로 지원자의 지원서를 변환하게 되면, 총 24개(3 * 2 * 2 * 2)의 노드만 검색하면, 코딩 테스트 점수를 제외하고 원하는 지원자를 찾을 수 있습니다.

 트리로 만들고 보니, 생각 보다 노드의 개수가 24개로 많지 않습니다. 개발언어, 직군, 경력, 소울푸드, 이 4가지를 모두 이어 붙여서 스트링으로 만들고, 딕셔너리의 키로 사용해서 시간복잡도를 계산해 보겠습니다. 코딩테스트 점수가 주어진 점수 이상인지는 바이너리 서치를 통해서 찾겠습니다.

O(10 ** 5 * 24 * log(5 ** 10 * 4)) -> O(2.4 * 10 * 6 * 15.xxxx) -> 약 O(10 ** 7)

시간복잡도가 충분히 작아졌으므로, 코딩을 해보겠습니다.

함수 solution의 인자의 이름이 리스트임으로 이름을 복수로 변경하겠습니다.

def solution(infos: List[str], queries: List[str]):

 

dict = defaultdict(list) for info in infos:     cjp, bf, js, cp, score = info.split(' ')     dict[cjp + bf + js + cp].append(int(score))

지원서를 저장할 딕셔너리 변수 dict를 만들구요, 코딩 테스트 점수르 저장하기위해서 list 형으로 만들었습니다. 개발언어, 직군, 경력, 소울푸드를 스트링으로 모두 더해서, 딕셔너리의 키로 사용합니다. 코딩테스트 점수만 숫자로 변환해서, 리스트에 넣어 줍니다.

 

for key in dict.keys():     dict[key].sort()

이후에 바이너리 서치를 통해서, 코딩 테스트 점수가 특정 점수 이상인 지원서의 개수를 찾기 때문에, 코딩 테스트 점수를 기준으로 모두 정렬해주어야 합니다.

 

alls = [['cpp', 'java', 'python'], ['backend', 'frontend'], ['junior', 'senior'], ['chicken', 'pizza']]

조건에 ‘-‘이 들어 있을 때, cartesian product를 사용해서, key를 만들게 되구요, cartesian product의 입력으로 사용할 리스트입니다.

 

for query in queries:     q = list(filter(lambda a: a != 'and', query.split(' ')))

조건을 키로 변환하는대 ‘and’ 스트링은 필요없으므로 filter()함수를 통해서 삭제합니다.

query가 ‘cpp and - and senior and pizza 250’ 라면 ‘and가 모두 삭제되고, q 에는 [‘cpp’, ‘-‘, ‘senior‘, ‘pizza‘, ‘250‘]이 저장 됩니다.

for idx in range(4):     if q[idx] == '-':         q[idx] = alls[idx]     else:         q[idx] = [q[idx]]

직군만 모든 직군(‘-‘)이 허용됩니다. for루프가 종료되면, q에는 [[‘cpp’], ['backend', 'frontend'], [‘senior‘], [‘pizza‘], [‘250‘]]이 저장됩니다.

score = int(q[4])

코딩 테스트 점수는 score변수에 저장합니다.

qs = list(product(q[0], q[1], q[2], q[3]))

리스트 q를 가지고 cartesian product를 실행하면, 아래 리스트가 리턴됩니다.

[[‘cpp’, 'backend', ‘senior‘, ‘pizza‘],

[‘cpp’, 'frontend', ‘senior‘, ‘pizza‘]]

keys = list(map(lambda a: ''.join(a), qs))

리스트의 각 아이템을 모두 붙여서, 딕셔너리에 사용할 키를 만들어 줍니다. key값은 아래와 같습니다.

[‘cppbackendseniorpizza‘, ‘cppfrontendseniorpizza‘]

local_answer = 0     for key in keys:         local_answer += binary_search(score, dict[key])     answer.append(local_answer) return answer

모든 key 마다 binary_search()함수를 호출해서, 코딩테스트 점수가 score이상이 지원서의 개수를 모두 더한 뒤에, answer에 추가하고 러턴하면, 이 문제의 답을 구할 수 있습니다.

 

궁금한 문제, 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

from typing import List from collections import defaultdict from itertools import product def solution(infos: List[str], queries: List[str]):     dict = defaultdict(list)     for info in infos:         cjp, bf, js, cp, score = info.split(' ')         dict[cjp + bf + js + cp].append(int(score))     for key in dict.keys():         dict[key].sort()     alls = [['cpp', 'java', 'python'], ['backend', 'frontend'], ['junior', 'senior'], ['chicken', 'pizza']]     answer = []     for query in queries:         q = list(filter(lambda a: a != 'and', query.split(' ')))         for idx in range(4):             if q[idx] == '-':                 q[idx] = alls[idx]             else:                 q[idx] = [q[idx]]         score = int(q[4])         qs = list(product(q[0], q[1], q[2], q[3]))         keys = list(map(lambda a: ''.join(a), qs))         local_answer = 0         for key in keys:             local_answer += binary_search(score, dict[key])         answer.append(local_answer)     return answer def binary_search(target: int, dt: List[int]):     begin, end = 0, len(dt) -1     while begin <= end:         mid = (begin + end) // 2         if dt[mid] < target:             begin = mid +1         else:             end = mid -1     return len(dt) - begin