카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
초기코드(시간초과)
def solution(info, query):
answer = []
temp = []
for i in info:
a = list(map(str, i.split()))
temp.append(a)
for i in query:
cnt = 0
a = list(map(str, i.split()))
for j in range(len(temp)):
if a[0] == temp[j][0] or a[0] == '-':
if a[2] == temp[j][1] or a[2] == '-':
if a[4] == temp[j][2] or a[4] == '-':
if a[6] == temp[j][3] or a[6] == '-':
if int(a[7]) <= int(temp[j][4]) or a[7] == '-':
cnt += 1
answer.append(cnt)
return answer너무 간단하게생각한탓인지 시간 초과가 나버렸다.
그도 그럴것이 제한사항에
- info 배열의 크기는 1 이상 50,000 이하입니다.
- query 배열의 크기는 1 이상 100,000 이하입니다.
라고 명시 되어있었다.
보통 1억회 이하로 되야지 효율성을 통과한다고 한다.
근데 내코드는 query를 돌면서 info도 돌기때문에 50000 * 100000 = 5억번 검사를 한다.
당연히 안된다.
2번째 시도
https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
이 유튜브도 참고했다
카카오 문제 해설 페이지를 참고해서 어떻게 풀어야할지 알게되었다.
나는 조건에 따라 하나하나 다 검사를 했다.
검사할 항목이 조금만 있으면 상관없는데 10만개면 얘기가 달라진다.
그래서 나올만한 경우의수에따라 점수를 분류하고
점수를 이진탐색으로 찾으면 시간내에 풀 수 있다고 생각했다.
이진탐색은 logN의 시간복잡도를 가지기 때문이다.
import bisect
language = ['cpp','java','python']
part = ['backend','frontend']
career = ['junior','senior']
food = ['chicken','pizza']
def calc(sorted_info,a,b,c,d,e):
cnt = 0
if a == '-':
for item in language:
cnt += calc(sorted_info,item,b,c,d,e)
elif b == '-':
for item in part:
cnt += calc(sorted_info,a,item,c,d,e)
elif c == '-':
for item in career:
cnt += calc(sorted_info,a,b,item,d,e)
elif d == '-':
for item in food:
cnt += calc(sorted_info,a,b,c,item,e)
else:
index = bisect.bisect_left(sorted_info[a][b][c][d],e)
cnt = len(sorted_info[a][b][c][d]) - index
return cnt
def solution(info, query):
answer = []
sorted_info = {}
for i in language:
sorted_info[i] = {}
for j in part:
sorted_info[i][j] = {}
for k in career:
sorted_info[i][j][k] = {}
for f in food:
sorted_info[i][j][k][f] = []
for i in info:
a,b,c,d,e = i.split()
sorted_info[a][b][c][d].append(int(e))
for a in language:
for b in part:
for c in career:
for d in food:
sorted_info[a][b][c][d].sort()
for q in query:
a, aa, b, bb, c, cc, d, e = q.split()
answer.append(calc(sorted_info, a, b, c, d, int(e)))
return answer'-'를 처리해주기위해서 재귀함수를 사용했다. (언어에서 '-'가 나올경우 모든언어에 대해 calc()함수 실행)
이진탐색
또 마지막 점수처리를 할때 이진탐색을 이용했는데
파이썬에는 이미 이진탐색라이브러리가 구현 되어있어 사용했다
사용방법은 이렇다.
import bisect
number = [10,20,30,40,50]
bisect.bisect_left(number,20) #값은 1대상배열과 기준값을 주면 기준값위치의 인덱스를 반환해준다!
기준값이 배열에 없어도 상관없다.
만약 이 라이브러리를 쓰지않고 이진 탐색을 구현했다면
number = [10,20,30,40,50]
n = 20
start = 0
end = len(number)-1
result = 0
while start <= end:
mid = (start + end) // 2
if number[mid] >= n:
result = mid
end = mid -1
else:
start = mid + 1 이런식으로 구현해야 했을 것이다.
