[Python/파이썬] 백준 1946번 신입 사원

https://www.acmicpc.net/problem/1946

코드

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    applicants = []
    for _ in range(n):
        doc, interview = map(int, input().split())
        heappush(applicants, (doc, interview))

    answer = 1
    comp_interview = heappop(applicants)[1]
    while applicants:
        now = heappop(applicants)
        if now[1] < comp_interview:
            comp_interview = now[1]
            answer += 1
    print(answer)

 

우선 서류심사 순위를 기준으로 지원자를 정렬합니다. 이때 최소힙을 사용하여 별도의 정렬 과정 없이 서류 순위가 높은 순부터 볼 수 있게 한다.

 

이제 applicants 힙에 있는 지원자들을 하나씩 뽑아서 기준점인 comp_interview 값과 뽑은 지원자의 면접 순위를 비교하여 뽑을지 말지 결정한다. 뽑는 대상은 면접 순위가 현재 기준인 comp_interview보다 순위가 높은 지원자이며, 지원자가 선발될 때마다 기준점을 뽑힌 대상자의 면접 순위로 갱신해준다.