사용자 도구

사이트 도구


ps:problems:programmers:72412

순위 검색

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호72412
문제명순위 검색
레벨Level 2
분류

구현, 이진검색

시간복잡도O((n+q)logn)
인풋사이즈n<=50000, q<=100000
사용한 언어Python
해결날짜2021/01/26
출처

ps:problems:programmers:2021_kakao_blind_recruitment

풀이

  • 알고리즘적으로 어려운 부분은 없고, 구현 문제에 가깝다.
  • 총 3*2*2*2 개의 타입으로 지원자를 분류 가능하므로, 각 타입별로 리스트를 따로 만들고, 각 리스트에는 점수를 정렬해서 저장한다. 쿼리가 들어오면 매칭되는 리스트들에서, 기준점수 이상의 지원자의 수를 이진검색으로 찾는다.
    • '-'에 해당되는 쿼리를 처리하기 위해서, 해당되는 2가지나 3가지의 타입에서 각각 지원자를 찾아서 더하는 방법으로 구현하긴 했는데, 그냥 '-' 에 대해서도 따로 리스트를 만들어주는 방법도 있다. 그편이 더 구현이 간단할 수도 있을 것 같다.
  • 타입의 갯수는 상수값이라고 생각하면, 각 리스트의 점수들을 정렬하는 데에, O(nlogn), 쿼리마다 이진검색을 해야 하므로 O(qlogn), 그래서 전체 O((n+q)logn)의 시간복잡도로 풀린다.

코드

"""Solution code for "Programmers 72412. 순위 검색".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72412
- Solution link: http://www.teferi.net/ps/problems/programmers/72412
"""

import bisect
import collections


def solution(info, query):
    scores_by_type = collections.defaultdict(list)
    for resume in info:
        *types, score = resume.split()
        scores_by_type[tuple(types)].append(int(score))
    for scores in scores_by_type.values():
        scores.sort()

    answer = []
    for q in query:
        q_list = q.split()
        type_filter = q_list[::2]
        score_filter = int(q_list[-1])
        count = sum(
            len(scores) - bisect.bisect_left(scores, score_filter)
            for types, scores in scores_by_type.items()
            if all(f in ['-', t] for f, t in zip(type_filter, types)))
        answer.append(count)

    return answer

토론

댓글을 입력하세요:
Z H Y L G
 
ps/problems/programmers/72412.txt · 마지막으로 수정됨: 2021/02/04 16:09 저자 teferi