[Boj] 신입사원 1946(python)

문제링크 : https://www.acmicpc.net/problem/1946

테스트 케이스 N이 주어지고, 신입사원 수와 그 후 신입사원 수 줄만큼 신입사원의 점수가 입력된다.

먼저, 신입사원 리스트를 첫 번째 항을 기준으로 정렬한다. 이 경우, 정렬된 신입사원 리스트의 첫 번째 항은 첫 번째 시험에서 가장 좋은 성적을 얻은 사람이다.

이를 채용 인원 리스트에 추가한다. 그 후 신입사원 리스트를 순회하면서, 신입사원의 두 번째 시험 성적과 채용 인원의 두 번째 시험과 비교하여 조건에 맞으면 추가한다.

결국, 매 순간에서 그 당시의 최적의 선택을 한다는 점에서 그리디 알고리즘 문제이었다.

import sys

N = int(sys.stdin.readline().rstrip())
for _ in range(N):
    len_employee = int(sys.stdin.readline().rstrip())
    employees = []
    for _ in range(len_employee):
        employee = list(map(int, sys.stdin.readline().split()))
        employees.append(employee)
    answer = []
    cnt = 0
    employees.sort(key=lambda x:x[0])
    answer.append(employees[0])
    for employee in employees[1:]:
        if answer[-1][1] > employee[1]:
            answer.append(employee)
    print(len(answer))