▶순위 검색 (Python) : 2021 KAKAO BLIND RECRUITMENT (level 2)
▶문제
- 코딩 테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
- 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
- 지원 경력 구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
- 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩 테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의 조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의 조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
▶제한 사항
- info 배열의 크기는 1 이상 50,000 이하입니다.
- info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩 테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
- query 배열의 크기는 1 이상 100,000 이하입니다.
- query의 각 문자열은 "[조건] X" 형식입니다.
- [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
- '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
- 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩 테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩 테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.
▶입출력 예제
지원자 정보를 표로 나타내면 다음과 같습니다.
- "java and backend and junior and pizza 100" : java로 코딩 테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩 테스트 점수를 100점 이상 받은 지원자는 1명입니다.
- "python and frontend and senior and chicken 200" : python으로 코딩 테스트를 봤으며, frontend 직군을 선택했고, senior 경력이면서 소울 푸드로 chicken을 선택한 지원자 중 코딩 테스트 점수를 200점 이상 받은 지원자는 1명입니다.
- "cpp and - and senior and pizza 250" : cpp로 코딩 테스트를 봤으며, senior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩 테스트 점수를 250점 이상 받은 지원자는 1명입니다.
- "- and backend and senior and - 150" : backend 직군을 선택했고, senior 경력인 지원자 중 코딩 테스트 점수를 150점 이상 받은 지원자는 1명입니다.
- "- and - and - and chicken 100" : 소울푸드로 chicken을 선택한 지원자 중 코딩 테스트 점수를 100점 이상을 받은 지원자는 2명입니다.
- "- and - and - and - 150" : 코딩 테스트 점수를 150점 이상 받은 지원자는 4명입니다.
▶풀이
처음에는 그냥 직관적으로 문제를 풀었다.
그러니까 결과는 정확성 테스트 통과, 효율성 테스트 실패.
def solution(info, query):
answer = []
for q in query:
q = q.replace('and ', '')
q = q.split()
count = 0
for i in info:
i = i.split()
flag = True
if int(i[4]) < int(q[4]):
flag = False
else:
for x in range(4):
if q[x] == '-':
continue
else:
if q[x] != i[x]:
flag = False
break
if flag:
count += 1
answer.append(count)
return answer
그래서 새로운 방식을 찾아보려고 노력해봤다.
하나하나 비교하면 당연히 시간을 많이 잡아먹을 것이라고 생각해서, 이진 탐색으로 하려고 맘먹었다.
여기서 쓴 함수가 bisect_left다.
일단 주어진 조건은 순서대로 나오기에,
점수를 나타내는 부분-val(information[-1])과 정보를 알려주는 부분-key(information[:-1])로 나눴다.
다음으로는 key의 모든 조합을 위해서 0~4까지 반복을 해주면서 combination함수를 이용했다.
그렇게 나온 조합들은 하나의 string으로 합쳤고, info_dic에 있는지 없는지 확인하며 넣어줬다. + 정렬도 해주면 된다.
다음으로는 query를 확인해주는데, info_dic을 만드는 방식과 비슷하다.
query에서 아까처럼 key, val로 나눈 다음 key를 하나로 합쳐준다.
거기서 'and'와 '-'는 replace를 이용해 ''로 바꿔서 없애준다.
그다음 info_dic에 있는지 없는지 확인 후 개수를 세주면 되는데, 이때 bisect_left를 사용한다.
bisect_left는 어떤 숫자가 주어진다면, 그 숫자가 몇 번째에 들어갈지 알려준다.
그럼 전체에서 그 값을 빼주면 자연스럽게 원하는 값 이상이 몇 개인지 알 수 있다.
https://docs.python.org/ko/3/library/bisect.html
bisect — 배열 이진 분할 알고리즘 — Python 3.10.6 문서
bisect — 배열 이진 분할 알고리즘 소스 코드: Lib/bisect.py 이 모듈은 정렬된 리스트를 삽입 후에 다시 정렬할 필요 없도록 관리할 수 있도록 지원합니다. 값비싼 비교 연산이 포함된 항목의 긴 리
docs.python.org
from itertools import combinations
from bisect import bisect_left
def solution(info, query):
answer = []
info_dic = {}
for i in range(len(info)):
information = info[i].split()
key = information[:-1]
val = int(information[-1])
for j in range(5):
for c in combinations(key, j):
tmp = ''.join(c)
if tmp in info_dic:
info_dic[tmp].append(val)
else:
info_dic[tmp] = [val]
for i in info_dic:
info_dic[i].sort()
for qu in query:
q = qu.split()
key = q[:-1]
val = int(q[-1])
key = ''.join(key)
key = key.replace('and', '')
key = key.replace('-', '')
if key in info_dic:
info_key = info_dic[key]
tmp = bisect_left(info_key, val)
answer.append(len(info_key) - tmp)
else:
answer.append(0)
return answer저렇게 문제를 해결해서 제출하면 정확성, 효율성 모두 통과가 된다.
level 2의 문제라서 직관적으로 풀어도 통과가 될 줄 알았는데, 그게 아니었다.
실제 코딩 테스트를 칠 때는 조금 더 신중하게 풀어서 시간을 단축시켜야겠다.
