문제 링크
문제 설명
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
- 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
- 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
- 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
- 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.- [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
로 질의했을때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
문제 풀이
시도 1
그냥 풀기는 쉽게 풀었는데 효율성을 하나도 통과하지 못했다
def solution(info, query):
answer = []
applicants = {}
for i in range(len(info)):
pl, job, career, food, score = info[i].split(" ")
applicants[i] = {1: pl, 2: job, 3: career, 4: food, 5: score}
for q in query:
count = 0
query_comp = []
for i in list(q.replace("and ", "").split(" ")):
if i != "-":
query_comp.append(i)
for applicant in applicants.values():
flag = True
for qc in query_comp[:-1]:
if qc not in applicant.values():
flag = False
break
if flag is True and int(applicant[5]) >= int(query_comp[-1]):
count += 1
answer.append(count)
return answer시도 2
not in 이 시간이 오래 걸리는 것 같아서 not in을 사용하지 않는 쪽으로 구현해봤는데 시간이 미세하게 줄어들뿐 효율성은 여전히 통과하지 못했다 ㅠ ㅠ
def solution(info, query):
answer = []
applicants = {}
for i in range(len(info)):
pl, job, career, food, score = info[i].split(" ")
applicants[i] = {0: pl, 1: job, 2: career, 3: food, 4: score}
for q in query:
count = 0
query_comp = list(q.replace("and ", "").split(" "))
for applicant in applicants.values():
flag = True
i = 0
for qc in query_comp[:-1]:
if qc != "-":
if qc != applicant[i]:
flag = False
break
i += 1
if flag is True and int(applicant[4]) >= int(query_comp[-1]):
count += 1
answer.append(count)
return answer시도 3
433*3의 크기를 가지는 dictionary에 각 지원자의 id를 저장해서 query별로 카운트하였는데 이거도 시간초과가 났다,,,,,, O(i + q) 아닌가,,
def solution(info, query):
answer = []
languages = ["cpp", "java", "python", "-"]
job_group = ["backend", "frontend", "-"]
career = ["junior", "senior", "-"]
food = ["chicken", "pizza", "-"]
applicants = {}
scores = []
for l in languages:
for j in job_group:
for c in career:
for f in food:
str1 = l+j+c+f
applicants[str1] = set()
for i in range(len(info)):
l, j, c, f, score = info[i].split(" ")
scores.append(score)
for ll in [l, "-"]:
for jj in [j, "-"]:
for cc in [c, "-"]:
for ff in [f, "-"]:
applicants[ll+jj+cc+ff].add(i)
for q in query:
count = 0
l, j, c, f, score = list(q.replace("and ", "").split(" "))
for a in applicants[l+j+c+f]:
if int(score) <= int(scores[a]):
count += 1
answer.append(count)
return answer시도 4
결국 모르겠어서 질문하기의 풀이 흐름을 보고 풀었다,, 캐어려움
- applicants 딕셔너리에 지원자의 모든 경우의 수(16가지=4!)를 key로 가지게 만든다.
for l in languages:
for j in job_group:
for c in career:
for f in food:
str1 = l+j+c+f
applicants[str1] = []- info를 돌면서 각 지원자의 조건을 파싱해서 해당 지원자가 해당될 수 있는 모든 key에 점수를 넣어준다.
ex. javabackendjuniorpizza의 경우에 -backendjuniorpizza, java-juniorpizza, ..., ----
for i in range(len(info)):
l, j, c, f, score = info[i].split(" ")
scores.append(score)
for ll in [l, "-"]:
for jj in [j, "-"]:
for cc in [c, "-"]:
for ff in [f, "-"]:
applicants[ll+jj+cc+ff].append(int(score))- query를 순회하면서 query 정보를 파싱하고, 해당 조건에 만족하는 지원자 중, score가 쿼리의 score보다 큰 지원자의 수를 이분탐색으로 센다.
-> 이분탐색이 시간을 줄일 수 있는 key였던듯,, 이분탐색 하기 위해서 applicants의 각 지원자 점수를 우선 정렬해줘야한다.
for a in applicants.values():
a.sort()
for q in query:
count = 0
l, j, c, f, score = list(q.replace("and ", "").split(" "))
idx = bisect_left(applicants[l+j+c+f], int(score))
answer.append(len(applicants[l+j+c+f]) - idx)전체 코드
def solution(info, query):
answer = []
languages = ["cpp", "java", "python", "-"]
job_group = ["backend", "frontend", "-"]
career = ["junior", "senior", "-"]
food = ["chicken", "pizza", "-"]
applicants = {}
scores = []
for l in languages:
for j in job_group:
for c in career:
for f in food:
str1 = l+j+c+f
applicants[str1] = []
for i in range(len(info)):
l, j, c, f, score = info[i].split(" ")
scores.append(score)
for ll in [l, "-"]:
for jj in [j, "-"]:
for cc in [c, "-"]:
for ff in [f, "-"]:
applicants[ll+jj+cc+ff].append(int(score))
for a in applicants.values():
a.sort()
for q in query:
count = 0
l, j, c, f, score = list(q.replace("and ", "").split(" "))
idx = bisect_left(applicants[l+j+c+f], int(score))
answer.append(len(applicants[l+j+c+f]) - idx)
return answer정말 어렵구만요,,
Hongik CE