문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 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점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.
[입출력 예]
infoqueryresult
info | query | result |
["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] | ["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"] | [1,1,1,1,2,4] |
입출력 예에 대한 설명
지원자 정보를 표로 나타내면 다음과 같습니다.
언어직군경력소울 푸드점수
언어 | 직군 | 경력 | 소울 푸드 | 점수 |
java | backend | junior | pizza | 150 |
python | frontend | senior | chicken | 210 |
python | frontend | senior | chicken | 150 |
cpp | backend | senior | pizza | 260 |
java | backend | junior | chicken | 80 |
python | backend | senior | chicken | 50 |
- "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명 입니다.
풀이
처음에는 직관적으로 for문을 이용해서 코드를 짰더니 정확성 테스트는 통과했지만 효율성 테스트를 통과하지 못했다. 입력받은 info와 query를 and와 -를 제외해서 공백을 기준으로 나눈 뒤 issubset함수를 이용해서 condition조건이 다 포함되는지 확인하는 방식으로 구현했다.
def solution(info, query):
answer = []
applicant = [[] for i in range(len(info))]
condition = [[] for i in range(len(query))]
for i in range(len(info)):
applicant[i].extend(info[i].split(' '))
for i in range(len(query)):
for j in query[i].split(' '):
if j != "and" and j != "-":
condition[i].append(j)
for i in range(len(condition)):
count = 0
for j in range(len(applicant)):
if set(condition[i][:-1]).issubset(set(applicant[j][:-1])) and int(condition[i][-1]) <= int(applicant[j][-1]):
count += 1
answer.append(count)
return answer
테스트 1 〉 통과 (0.34ms, 10.4MB)
테스트 2 〉 통과 (0.17ms, 10.4MB)
테스트 3 〉 통과 (1.45ms, 10.4MB)
테스트 4 〉 통과 (14.41ms, 10.5MB)
테스트 5 〉 통과 (65.44ms, 10.6MB)
테스트 6 〉 통과 (154.84ms, 10.8MB)
테스트 7 〉 통과 (74.16ms, 11.1MB)
테스트 8 〉 통과 (343.10ms, 12.5MB)
테스트 9 〉 통과 (363.39ms, 12.6MB)
테스트 10 〉 통과 (361.65ms, 12.7MB)
테스트 11 〉 통과 (61.57ms, 10.6MB)
테스트 12 〉 통과 (155.00ms, 10.7MB)
테스트 13 〉 통과 (73.67ms, 11.2MB)
테스트 14 〉 통과 (321.55ms, 11.5MB)
테스트 15 〉 통과 (371.14ms, 11.4MB)
테스트 16 〉 통과 (64.87ms, 10.7MB)
테스트 17 〉 통과 (160.35ms, 10.7MB)
테스트 18 〉 통과 (356.55ms, 11.4MB)
info배열은 50000까지, query배열은 100000까지 존재하므로 단순하게 for문을 이용해서 코드를 짜면 O(50000 * 100000)의 시간복잡도가 나오므로 효율성 테스트를 통과하기 위해 applicant를 코딩테스트 점수를 기준으로 정렬한 뒤 lower bound를 이용하여 개발팀이 원하는 코딩테스트 점수 이상의 지원자에 한해서만 남은 요소를 비교하도록 바꿔줬다. 위의 방법에 비해 1/2넘게 시간이 줄었지만 효율성 테스트는 통과하지 못했다.
def solution(info, query):
answer = []
applicant = [[] for i in range(len(info))]
condition = [[] for i in range(len(query))]
for i in range(len(info)):
applicant[i].extend(info[i].split(' '))
for i in range(len(query)):
for j in query[i].split(' '):
if j != "and" and j != "-":
condition[i].append(j)
applicant.sort(key=lambda x:int(x[-1]))
for i in range(len(condition)):
left, right, target = 0, len(applicant)-1, int(condition[i][-1])
while(left < right):
mid = (left+right)//2
if target <= int(applicant[mid][-1]):
right = mid
else:
left = mid+1
count = 0
for j in range(right, len(applicant)):
if set(condition[i][:-1]).issubset(set(applicant[j][:-1])):
count += 1
answer.append(count)
return answer
테스트 1 〉 통과 (0.14ms, 10.3MB)
테스트 2 〉 통과 (0.13ms, 10.5MB)
테스트 3 〉 통과 (0.99ms, 10.4MB)
테스트 4 〉 통과 (10.21ms, 10.5MB)
테스트 5 〉 통과 (40.19ms, 10.7MB)
테스트 6 〉 통과 (76.25ms, 10.6MB)
테스트 7 〉 통과 (37.37ms, 11.1MB)
테스트 8 〉 통과 (190.00ms, 12.6MB)
테스트 9 〉 통과 (171.76ms, 13MB)
테스트 10 〉 통과 (190.56ms, 13MB)
테스트 11 〉 통과 (36.94ms, 10.5MB)
테스트 12 〉 통과 (77.33ms, 10.7MB)
테스트 13 〉 통과 (36.34ms, 11MB)
테스트 14 〉 통과 (156.70ms, 11.6MB)
테스트 15 〉 통과 (150.55ms, 11.6MB)
테스트 16 〉 통과 (35.04ms, 10.6MB)
테스트 17 〉 통과 (74.16ms, 10.5MB)
테스트 18 〉 통과 (145.73ms, 11.5MB)
여러 방법을 써도 자꾸 유효성 검사 통과가 안돼서 결국 문제 해설을 확인하고 힌트를 얻었다.
https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/
아래와 같이 info가 들어오면 query에서 true값이 나오는 모든 경우의 수를 group형태로 만들어서 key로 저장하고 점수를 value로 저장해둔 뒤 query가 들어오면 해당 값을 key로 value에 저장되어 있는 점수 리스트 중 조건에 알맞는 개수를 세서 return해주면 된다. 이 때, lower bound를 써서 개수를 세면 속도가 더 빨라진다.
언어 | 직군 | 경력 | 소울 푸드 | 점수 |
java | backend | junior | pizza | 150 |
– | backend | junior | pizza | 150 |
java | – | junior | pizza | 150 |
java | backend | – | pizza | 150 |
java | backend | junior | – | 150 |
– | – | junior | pizza | 150 |
– | backend | – | pizza | 150 |
… (생략) | ||||
java | – | – | – | 150 |
– | – | – | – | 150 |
from collections import defaultdict
def solution(info, query):
answer = []
group = defaultdict(list)
#점수를 제외한 값을 key, 점수 리스트를 value로 group생성
for i in range(len(info)):
tmp = info[i].split(' ')
group[tmp[0]+tmp[1]+tmp[2]+tmp[3]].append(int(tmp[4]))
group['-'+tmp[1]+tmp[2]+tmp[3]].append(int(tmp[4]))
group['-'+'-'+tmp[2]+tmp[3]].append(int(tmp[4]))
group['-'+tmp[1]+'-'+tmp[3]].append(int(tmp[4]))
group['-'+tmp[1]+tmp[2]+'-'].append(int(tmp[4]))
group['-'+'-'+'-'+tmp[3]].append(int(tmp[4]))
group['-'+'-'+tmp[2]+'-'].append(int(tmp[4]))
group['-'+tmp[1]+'-'+'-'].append(int(tmp[4]))
group['-'+'-'+'-'+'-'].append(int(tmp[4]))
group[tmp[0]+'-'+tmp[2]+tmp[3]].append(int(tmp[4]))
group[tmp[0]+'-'+'-'+tmp[3]].append(int(tmp[4]))
group[tmp[0]+'-'+'-'+'-'].append(int(tmp[4]))
group[tmp[0]+'-'+tmp[2]+'-'].append(int(tmp[4]))
group[tmp[0]+tmp[1]+'-'+tmp[3]].append(int(tmp[4]))
group[tmp[0]+tmp[1]+'-'+'-'].append(int(tmp[4]))
group[tmp[0]+tmp[1]+tmp[2]+'-'].append(int(tmp[4]))
for value in group.values():
value.sort()
#group의 key에서 해당 query가 있는지 확인 후 이진 탐색으로 인원수세기
for i in range(len(query)):
query[i] = [i for i in query[i].split() if i != 'and']
q_key = query[i][0]+query[i][1]+query[i][2]+query[i][3]
q_score = int(query[i][4])
if q_key in group:
i_score = group[q_key]
left, right, target = 0, len(i_score)-1, q_score
if i_score[-1] >= q_score:
while(left < right):
mid = (left+right)//2
if target <= i_score[mid]:
right = mid
else:
left = mid+1
answer.append(len(group[q_key]) - right)
else:
answer.append(0)
else:
answer.append(0)
return answer
테스트 1 〉 통과 (0.19ms, 10.3MB)
테스트 2 〉 통과 (0.20ms, 10.6MB)
테스트 3 〉 통과 (0.55ms, 10.4MB)
테스트 4 〉 통과 (2.05ms, 10.6MB)
테스트 5 〉 통과 (3.51ms, 10.7MB)
테스트 6 〉 통과 (7.16ms, 10.5MB)
테스트 7 〉 통과 (5.21ms, 11.2MB)
테스트 8 〉 통과 (37.81ms, 11.5MB)
테스트 9 〉 통과 (41.16ms, 13.1MB)
테스트 10 〉 통과 (41.99ms, 13.8MB)
테스트 11 〉 통과 (3.85ms, 10.8MB)
테스트 12 〉 통과 (7.05ms, 10.9MB)
테스트 13 〉 통과 (5.28ms, 11.2MB)
테스트 14 〉 통과 (23.97ms, 12.1MB)
테스트 15 〉 통과 (25.10ms, 12.2MB)
테스트 16 〉 통과 (3.50ms, 10.6MB)
테스트 17 〉 통과 (7.64ms, 10.7MB)
테스트 18 〉 통과 (24.36ms, 12.2MB)
테스트 1 〉 통과 (880.49ms, 88.8MB)
테스트 2 〉 통과 (1039.00ms, 89.1MB)
테스트 3 〉 통과 (1003.83ms, 75.8MB)
테스트 4 〉 통과 (977.12ms, 77.1MB)
배열의 인덱스에 접근하는데도 생각보다 많은 시간이 드는 듯 하다. 계속 효율성 테스트를 통과 못해서 이진탐색하는 부분의 배열 접근을 줄였더니 통과할 수 있었다. group을 생성하는 부분은 시간을 조금이라도 줄이기 위해 모든 경우의 수를 직접 적어주었다.
i_score 배열에 조건을 만족하는 score가 없을 시에 answer에 0을 넣어야 하는데 이 부분을 생각하지 못해서.. 헤매기도 했다..ㅎ
'코딩 > Programmers' 카테고리의 다른 글
[프로그래머스] 광고 삽입 (0) | 2021.09.08 |
---|---|
[프로그래머스] 합승 택시 요금 (0) | 2021.09.05 |
[프로그래머스] 메뉴 리뉴얼(Level 2) (0) | 2021.08.22 |
[프로그래머스] 입국심사(Level 3) (0) | 2021.08.19 |
[프로그래머스] 가장 먼 노드(Level 3) (1) | 2021.08.17 |