[programmers] 순위 검색

김우경·2021년 2월 13일
0

알고리즘

목록 보기
58/69

문제 링크

순위 검색

문제 설명

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 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

결국 모르겠어서 질문하기의 풀이 흐름을 보고 풀었다,, 캐어려움

  1. 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] = []
  1. 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))
  1. 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

정말 어렵구만요,,

profile
Hongik CE

0개의 댓글