백준 알고리즘 1946번 신입 사원 - 파이썬

www.acmicpc.net/problem/1946

1946번: 신입 사원

그리디 알고리즘.

먼저, 서류 순위를 기준으로 정렬을 해준다. 서류 1등은 무조건 뽑히기 때문에 서류 1등의 면접 순위를 기준으로 나머지 지원자들의 면접 순위 비교를 진행한다. 참고로 문제에서 주어지는 값은 성적이 아닌 순위이다. 계속 성적으로 생각하며 문제 풀이하다가 깨닫고 고쳐서 정답판정을 받았다.

아 시간 초과도 발생하였는데 input 을 sys.stdin.readline 으로 치환해 해결하였다.

import sys
input = sys.stdin.readline

for tc in range(int(input())):
    n = int(input())
    appliers = []
    for _ in range(n):
        appliers.append(list(map(int, input().split())))

    appliers.sort(key=lambda x: x[0])
    result = 1
    temp = appliers[0][1]
    for i in range(1, n):
        if temp > appliers[i][1]:
            result += 1
            temp = appliers[i][1]

    print(result)