문제를 정리해보자.
카카오는 하반기 경력 개발자 공개채용을 진행 중이다. 현재 지원서 접수와 코딩테스트가 종료되었다.
이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였다.
항목은 아래와 같다.
개발언어: cpp, java, python
지원 직군: backend, frontend
지원 경력: junior, senior
소울푸드: chicken, pizza
코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에게 제공하기 위해
지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인지 쉽게 알 수 있는 도구를 만들어보자.
개발팀에서 궁금해하는 내용: '[조건]을 만족하는 사람 중 코딩테스트 점수 X점 이상 받은 사람은 모두 몇 명인가?'
예) 코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?
예) 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
+
풀이를 생각해보자.
info는 최대 50,000이다. (지원자)
query는 최대 100,000개이다. (조건)
만약 query마다 해당하는 info를 확인할 경우 최대 5,000,000,000번이다. (50,000 X 100,000)
따라서 선형탐색은 안된다.
지원자가 지원서에 입력한 4가지 항목으로 만들 수 있는 경우의 수는 몇 개일까?
(각 항목은 "-"의 경우일 고려해서 1을 더해준다.)
{'cppbackendjuniorchicken': [],
'cppbackendjuniorpizza': [],
.
.
.
'--seniorpizza': [],
'--senior-': [],
'---chicken': [],
'---pizza': [],
'----': []}
총 108개이다.
그렇다면 한 지원자는 108가지 중에서 몇 개의 경우에 해당할까?
16가지 경우에 해당한다. 예를 들어보자.
지원자가 java backend junior pizza 150라면?
아래 경우에 모두 해당한다.
1. javabackendjuniorpizza
2. javabackendjunior-
3. javabackend-pizza
4. javabackend--
5. java-juniorpizza
6. java-junior-
7. java--pizza
8. java---
9. -backendjuniorpizza
10. -backendjunior-
11. -backend-pizza
12. -backend--
13. --juniorpizza
14. --junior-
15. ---pizza
16. ----
자, 그럼 각 지원자들을 108가지 경우에 분류해서 그룹화하자.
(이렇게 한다면 조건마다 해당하는 지원자를 찾으려고 모든 지원자를 탐색하는 일이 발생하지 않는다.)
그리고 해당 조건의 그룹의 지원자들 점수를 가지고 기준을 넘는 지원자가 몇 명인지 확인하자.
(이도 마찬가지로, 선형 탐색을 할 경우 최대 5,000,000,000번이다. 시간복잡도 O(logN)인 이진탐색을 이용해서 찾도록 하자.)
구현해보자. (정확도 100%, 효율성 100%)
이진탐색의 경우, 그룹의 지원자들 점수에서 기준보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 한다. (lower bound)
def solution(infos, queries):
answer = []
# 총 경우의 수 (108가지)
info_dict = {}
for lang in ['cpp', 'java', 'python', "-"]:
for job in ['backend', 'frontend', "-"]:
for career in ['junior', 'senior', "-"]:
for food in ['chicken', 'pizza', "-"]:
info_dict[lang + job + career + food] = []
# 지원자의 경우의 수 (1인, 16가지)
for info in infos:
info = info.split(" ")
for lang in [info[0], "-"]:
for job in [info[1], "-"]:
for career in [info[2], "-"]:
for food in [info[3], "-"]:
info_dict[lang + job + career + food].append(int(info[4]))
for key in info_dict.keys():
info_dict[key].sort()
# 조건
for query in queries:
query = query.replace(" and ", "")
query = query.split()
query_score = int(query[1])
query = query[0]
# 점수
info_score = info_dict[query]
l = len(info_score)
tmp = l
low, high = 0, l - 1
while low <= high:
mid = (low + high) // 2
if query_score <= info_score[mid]:
tmp = mid
high = mid - 1
else:
low = mid + 1
answer.append(l - tmp)
return answer
print(solution(["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"]))
구현해보자. (정확도 100%, 효율성 0%)
처음에 시도한 방법이고 효율성에서 0점을 맞았다.
위와 같은 지원자 정보가 있다고 하자.
먼저, 점수는 새로운 리스트에 행과 같은 숫자의 index에 넣어주었다.
[150, 210, 150, 260, 80, 50]
그리고 위 사진과 같이 행의 index로 항목 별 조건에 그룹화했다.
그 다음 조건에 맞게 교집합을 구했다.
지원자가 java backend junior pizza 150라면?
1. [[150, 0], [210, 1], [150, 2], [260, 3], [80, 4], [50, 5]]
→ [[50, 5], [80, 4], [150, 0], [150, 2], [210, 1], [260, 3]]
→ [[150, 0], [150, 2], [210, 1], [260, 3]]
2. [[150, 0], [150, 2], [210, 1], [260, 3]] → java ∩ backend ∩ backend ∩ pizza = 0
import numpy
def BSearch(l, target, num_li):
check = l
low = 0
high = l - 1
while low <= high:
mid = (low + high) // 2
if int(target) <= num_li[mid][0]:
check = mid
high = mid - 1
else:
low = mid + 1
return num_li[check:]
def solution(info, query):
dic = {'cpp': [], 'java': [], 'python': [], 'backend': [], 'frontend': [], 'junior': [],
'senior': [], 'chicken': [], 'pizza': []}
answer = []
# 지원자
num_li = []
for idx, info_li in enumerate(info):
info_li = info_li.split(" ")
for i in range(5):
# 점수
if i == 4:
num_li.append([int(info_li[i]), idx])
# 점수 외
else:
dic[info_li[i]].append(idx)
num_li.sort()
# 지원조건
for query_li in query:
query_li = query_li.replace(" and ", " ")
query_li = query_li.split(" ")
# 점수(이진탐색)
tmp = BSearch(len(num_li), query_li[4], num_li)
if not tmp:
result = set({})
else:
result = set(numpy.array(tmp).T[1])
# 점수 외
for i in range(4):
if query_li[i] != '-':
result = result & set(dic[query_li[i]])
answer.append(len(result))
return answer
print(solution(["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"]))
하지만 시간초과로 통과하지 못했다.
시행착오
아래 코드는 정답코드와 유사한 코드이다. 하지만 특정 부분 때문에 계속 효율성에서 0점이 나왔다.
문제는 for query in queries: 해당 반목문 안에서 info_score = sorted(info_dict[query])로 점수들을 오름차순으로 정렬한 점이다. 이런 경우 반복문 내에서 정렬을 계속적으로 수행하기 때문에 효율성이 떨어진다.
따라서 info 정보를 바탕으로 해시맵을 형성한 후 점수들을 오름차순으로 정렬하는 로직을 먼저 넣어야 한다.
def solution(infos, queries):
answer = []
# 총 경우의 수 (108가지)
info_dict = {}
for lang in ['cpp', 'java', 'python', "-"]:
for job in ['backend', 'frontend', "-"]:
for career in ['junior', 'senior', "-"]:
for food in ['chicken', 'pizza', "-"]:
info_dict[lang + job + career + food] = []
# 지원자의 경우의 수 (1인, 16가지)
for info in infos:
info = info.split(" ")
for lang in [info[0], "-"]:
for job in [info[1], "-"]:
for career in [info[2], "-"]:
for food in [info[3], "-"]:
info_dict[lang + job + career + food].append(int(info[4]))
# 시간초과를 해결한 방법
# for key in info_dict.keys():
# info_dict[key].sort()
# 조건
for query in queries:
query = query.replace(" and ", "")
query = query.split()
query_score = int(query[1])
query = query[0]
# 점수
info_score = sorted(info_dict[query]) # 시간초과가 나는 부분
l = len(info_score)
tmp = l
low, high = 0, l - 1
while low <= high:
mid = (low + high) // 2
if query_score <= info_score[mid]:
tmp = mid
high = mid - 1
else:
low = mid + 1
answer.append(l - tmp)
return answer
print(solution(["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"]))
다른 사람 풀이 (정확도 100%, 효율성 100%)
다른 사람 풀이를 참고해서 코드를 수정해봤다.
1. defaultdict을 사용해서 180가지 경우의 수를 만들지 않았다.
2. combinations를 사용해서 16가지 경우의 수를 만들었다.
from collections import defaultdict
from itertools import combinations as combi
def solution(infos, queries):
info_dict = {}
answer = []
# 총 경우의 수 (108가지)
info_dict = defaultdict(list)
# # 지원자의 경우의 수 (1인, 16가지)
for info in infos:
info = info.split()
info_key = info[:-1]
info_val = int(info[-1])
for i in range(5):
for c in combi(info_key, i):
tmp_key = ''.join(c)
info_dict[tmp_key].append(info_val)
for key in info_dict.keys():
info_dict[key].sort()
# 조건
for query in queries:
query = query.replace(" and ", "")
query = query.replace("-", "")
query = query.split()
query_score = int(query[-1])
if len(query) == 1:
query = ""
else:
query = query[0]
# 점수
if query in info_dict:
info_score = info_dict[query]
if len(info_score) > 0:
l = len(info_score)
tmp = l
low, high = 0, l - 1
while low <= high:
mid = (low + high) // 2
if query_score <= info_score[mid]:
tmp = mid
high = mid - 1
else:
low = mid + 1
answer.append(l - tmp)
else:
answer.append(0)
return answer
print(solution(["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"]))
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 합승 택시 요금 (0) | 2022.03.20 |
|---|---|
| [프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 메뉴 리뉴얼 (0) | 2022.03.05 |
| [프로그래머스][2021 KAKAO BLIND RECRUITMENT][Python] 신규 아이디 추천 (0) | 2022.02.22 |
| [프로그래머스][2021 Dev-Matching: 웹 백앤드 개발자(상반기)][Python] 다단계 칫솔 판매 (0) | 2022.02.21 |
| [프로그래머스][2021 Dev-Matching: 웹 백앤드 개발자(상반기)][Python] 로또의 최고 순위와 최저 순위 (0) | 2022.02.21 |
