[프로그래머스/Python] 순위 검색

문제 설명

---

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

---

문제 풀이

---

처음 문제를 생각했을 때 info * query를 하게 되면 5만 * 10만으로 TLE가 나올 것 같아서 해쉬 테이블을 이용했으나, 여전히 코딩 점수가 높은 사람만 추리는 부분에서 시간을 너무 사용해서  정확성은 만점이 나왔으나 효율성 시간 초과가 나왔다.

 

이후 도저히 효율성을 해결할 방법을 몰라서 정답지를 찾아보고 코드를 수정해 아래와 같이 작성했다.

---

코   드

---

이전 코드

이전코드

from collections import defaultdict

def solution(info, queries):
    answer = []
    beforeScore = []
    wantScore = []
    language = defaultdict(set)
    group = defaultdict(set)
    career = defaultdict(set)
    food = defaultdict(set)
    codingTest = defaultdict(int)
    
    for idx, person in enumerate(info):
        l, g, cr, f ,ct = person.split(" ")
        language[l].add(idx)
        language["-"].add(idx)
        
        group[g].add(idx)
        group["-"].add(idx)
        
        career[cr].add(idx)
        career["-"].add(idx)
        
        food[f].add(idx)
        food["-"].add(idx)
        
        codingTest[idx] = int(ct)

    for query in queries:
        lang, grp, cr, fd_ct = query.split(" and ")
        fd, ct = fd_ct.split(" ")
        tmp = list(language[lang] & group[grp] & career[cr] & food[fd])
        cnt = list(filter(lambda x: codingTest[x] >= int(ct), tmp))
        answer.append(len(cnt))
    return answer

import bisect
from collections import defaultdict
def solution(info, query):
    answer = []
    people = defaultdict(list)
    
    for i in info:
        i = i.split()
        for lang in [i[0], "-"]:
            for job in [i[1], "-"]:
                for career in [i[2], "-"]:
                    for food in [i[3], "-"]:
                        people[(lang,job,career,food)].append(int(i[4]))
    
    for key in people:
        people[key].sort()
    
    for q in query:
        q = q.split()
        tmp = people[(q[0], q[2], q[4], q[6])]

        cnt = bisect.bisect_left(tmp, int(q[7]))
        answer.append(len(tmp) - cnt)
    return answer

---

느낀점: 해쉬맵을 하나로 통일해서 사용하는 것과 이진 탐색을 해야하는 것은 전혀 생각도 못했다. 아직 갈 길이 멀다.

링크: https://school.programmers.co.kr/learn/courses/30/lessons/72412

프로그래머스