문제 설명
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 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점 이상 받은 사람은 모두 몇 명인가?
즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.
* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?문제
지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
-
info 배열의 크기는 1 이상 50,000 이하입니다.
-
info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
- 개발언어는 cpp, java, python 중 하나입니다.
- 직군은 backend, frontend 중 하나입니다.
- 경력은 junior, senior 중 하나입니다.
- 소울푸드는 chicken, pizza 중 하나입니다.
- 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
-
query 배열의 크기는 1 이상 100,000 이하입니다.
-
query의 각 문자열은 "[조건] X" 형식입니다.
- [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
- 언어는 cpp, java, python, - 중 하나입니다.
- 직군은 backend, frontend, - 중 하나입니다.
- 경력은 junior, senior, - 중 하나입니다.
- 소울푸드는 chicken, pizza, - 중 하나입니다.
- '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
- X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- 예를 들면, "cpp and - and senior and pizza 500"은 cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?를 의미합니다.
입출력 예
첫 번째 풀이 - 효율성 실패
def solution(info, query):
answer = []
languages = {"java": set(), "python": set(), "cpp": set()}
job_group = {"frontend": set(), "backend": set()}
career = {"junior": set(), "senior": set()}
food = {"pizza": set(), "chicken": set()}
table = [languages, job_group, career, food]
# info 배열 내 문자열 키워드 추출
for i in range(len(info)):
info[i] = info[i].split()
languages[info[i][0]].add(i)
job_group[info[i][1]].add(i)
career[info[i][2]].add(i)
food[info[i][3]].add(i)
# query 배열 내 문자열 키워드 추출
for i in range(len(query)):
query[i] = query[i].replace(" and ", ' ')
query[i] = query[i].split()
for i in range(len(query)):
candidate = set(idx for idx in range(len(info)))
# 하나의 query에 해당하는 지원자 번호 찾기
for j in range(len(table)):
if query[i][j] != '-':
candidate &= table[j][query[i][j]]
# 해당 query의 조건을 만족하는 지원자 수 구하기
count = 0
for idx in candidate:
if int(info[idx][-1]) >= int(query[i][-1]):
count += 1
answer.append(count)
return answer첫 번째 접근
모든 조건을 만족하는 사람을 찾는 일이니, 각 조건별로 사람을 저장해놓고 교집합으로 사람을 구하면 되지 않을까하는 생각으로 풀었다.
그래서 각 조건 별로 딕셔너리를 통해 저장하고 마지막에 score만 따로 비교하여 조건을 만족하는 사람 수를 구했다.
다만, 효율성에서 시간초과가 났다. 솔직히 코드를 짜고 나서 보니 시간초과가 날 것이라는 예상은 했다. 그래서 이 코드를 더 효율적으로 짜는 방법을 찾아보았다.
찾아낸 접근법
위 링크를 타고 들어가면 답변으로 새로운 접근법을 제시해준다. 딕셔너리에 key 값으로 해당 info가 만족시킬 수 있는 문자열의 종류를 모두 key로 한 다음, score를 value에 있는 배열에 추가한다.
이때, 하나의 문자열(info)은 총 16개의 경우를 표현할 수 있다. 이것은 score 항목을 제외한 각 4개의 항목이 '-'로 대체되느냐 아니냐를 두고 2의 4승이 되므로 총 16개가 나오기 때문이다.
이렇게 딕셔너리를 만들었다면, query에서 문자열을 꺼내와 파싱한 후, 해당 문자열을 key로 하는 value를 가져온다.
당연히 배열이 나올테고, 자신이 원하는 score를 이분탐색으로 찾으면 된다. 이때, 이분탐색은 bisect 모듈을 사용하는 것이 좋다.
그렇게 완성한 정답
from itertools import product
from bisect import bisect_left
def get_all_possibility(info):
table = {}
for data in info:
data = data.split()
language = [data[0], "-"]
job_group = [data[1], "-"]
career = [data[2], "-"]
food = [data[3], "-"]
keys = list(map(''.join, product(language, job_group, career, food)))
for key in keys:
if key in table:
table[key].append(int(data[4]))
else:
table[key] = [int(data[4])]
return table
def score_sort(table):
for key, value in table.items():
table[key] = sorted(value)
def query_parsing(query):
query = query.replace(" and ", ' ')
index = query.rfind(' ')
key = ''.join(query[:index].split())
score = int(query[index + 1:])
return key, score
def solution(info , query):
answer = []
table = get_all_possibility(info)
score_sort(table)
for q in query:
key, score = query_parsing(q)
try:
candidate = table[key]
index = bisect_left(candidate, score)
answer.append(len(candidate) - index)
except KeyError:
answer.append(0)
return answer해결 과정
한 지원자의 모든 가능성 구하기
from itertools import product
def get_all_possibility(info):
table = {}
for data in info:
data = data.split()
language = [data[0], "-"]
job_group = [data[1], "-"]
career = [data[2], "-"]
food = [data[3], "-"]
keys = list(map(''.join, product(language, job_group, career, food)))
for key in keys:
if key in table:
table[key].append(int(data[4]))
else:
table[key] = [int(data[4])]
return table한 지원자의 정보가 담긴 문자열을 '공백 문자'를 기준으로 파싱한다. 이후, 모든 가능성을 구하기 위해 중복 순열을 지원하는 product를 사용한다.
이후, 해당 key가 table에 있다면 지원자의 점수를 배열에 추가하고, 아니라면 지원자의 점수를 가지고 있는 배열을 추가한다.
점수 배열 정렬
def score_sort(table):
for key, value in table.items():
table[key] = sorted(value)이분탐색을 하기 위해서는 배열이 정렬된 상태여야 하므로, 각 key에 해당하는 배열을 모두 오름차순으로 정렬한다.
query 파싱하기
def query_parsing(query):
query = query.replace(" and ", ' ')
index = query.rfind(' ')
key = ''.join(query[:index].split())
score = int(query[index + 1:])
return key, score이후, query 문장에서 key와 점수를 파싱한다. key와 점수는 가장 오른쪽에 있는 공백 문자를 기준으로 왼쪽은 key, 오른쪽은 점수라는 점을 생각하면 쉽게 파싱할 수 있다.
query를 만족하는 지원자 수 구하기
from bisect import bisect_left
answer = []
for q in query:
key, score = query_parsing(q)
try:
candidate = table[key]
index = bisect_left(candidate, score)
answer.append(len(candidate) - index)
except KeyError:
answer.append(0)구한 key 값으로 table에서 점수가 담긴 배열을 가져온다. 이때, 어떠한 지원자도 만족할 수 없는 key가 있을 수 있으므로 try로 감싸야 한다. 이때 KeyError가 발생했다면 answer에 0을 넣으면 된다.
만약 key가 존재한다면 bisect_left 메서드를 사용한다. 이 메서드는 첫 번째 인자로 전달된 배열의 정렬 상태를 유지하면서 두 번째로 전달된 인자를 삽입할 위치를 찾는다.
이때, 구해지는 인덱스는 두 번째로 전달된 인자를 해당 인덱스에 삽입했을 때, 왼쪽으로는 모두 자신보다 작은 값이라는 것이다.
고로 해당 인덱스 값을 len(candidate)에서 빼주면 해당 score 이상의 지원자의 수를 구할 수 있다.
다른 사람의 풀이
from itertools import combinations
def solution(info, query):
answer = []
db = {}
for i in info: # info에 대해 반복
temp = i.split()
conditions = temp[:-1] # 조건들만 모으고, 점수 따로
score = int(temp[-1])
for n in range(5): # 조건들에 대해 조합을 이용해서
combi = list(combinations(range(4), n))
for c in combi:
t_c = conditions.copy()
for v in c: # '-'를 포함한 새로운 조건을 만들어냄.
t_c[v] = '-'
changed_t_c = '/'.join(t_c)
if changed_t_c in db: # 모든 조건의 경우에 수에 대해 딕셔너리
db[changed_t_c].append(score)
else:
db[changed_t_c] = [score]
for value in db.values(): # 딕셔너리 내 모든 값 정렬
value.sort()
for q in query: # query의 모든 조건에 대해서
qry = [i for i in q.split() if i != 'and']
qry_cnd = '/'.join(qry[:-1])
qry_score = int(qry[-1])
if qry_cnd in db: # 딕셔너리 내에 값이 존재한다면,
data = db[qry_cnd]
if len(data) > 0:
start, end = 0, len(data) # lower bound 알고리즘 통해 인덱스 찾고,
while start != end and start != len(data):
if data[(start + end) // 2] >= qry_score:
end = (start + end) // 2
else:
start = (start + end) // 2 + 1
answer.append(len(data) - start) # 해당 인덱스부터 끝까지의 갯수가 정답
else:
answer.append(0)
return answerproduct를 사용하지 않고, combinations를 통해서도 해결할 수 있다. product를 사용하기 위해서는 각 항목별로 배열을 만들어야 하니, 항목이 많다면 배열을 만드는 것도 일이 될 수 있다.
