[백준] 1946번 : 신입 사원 (파이썬)

문제

나의 첫번째 답안

t=int(input())

for i in range(t):
    n=int(input())
    p=[]
    cnt=1
    
    for j in range(n):
        grade,rank=map(int,input().split())#성적, 면접순위
        p.append([grade,rank])

    p.sort()#성적으로 정렬하기
    mn=p[0][1]#성적이 1등인 사람의 면접 순위를 저장

    for k in range(1,n):#1등을ㅇ 제외하고
        if mn>p[k][1]:#2등부터 n등까지 면접순위 비교, mn이 더 크다면
            cnt+=1#인원수 증가
            mn=p[k][1]#해당 값으로 mn 초기화
    print(cnt)

시간 초과라는 결과가 나왔다.
반복문이 여러개이고, 입출력이 계속 일어나므로 sys.stdin.readline로 입출력 시간을 단축해주어야 한다.

나의 최종 답안

import sys
input=sys.stdin.readline

t=int(input())

for i in range(t):
    n=int(input())
    p=[]
    cnt=1
    
    for j in range(n):
        grade,rank=map(int,input().split())#성적, 면접순위
        p.append([grade,rank])

    p.sort()#성적으로 정렬하기
    mn=p[0][1]#성적이 1등인 사람의 면접 순위를 저장

    for k in range(1,n):#1등을 제외하고
        if mn>p[k][1]:#2등부터 n등까지 면접순위 비교, mn이 더 크다면
            cnt+=1#인원수 증가
            mn=p[k][1]#해당 값으로 mn 초기화
    print(cnt)

접근 방법

• 최댓값 구하는 방식과 비슷하게 접근할 수 있다.(그리디 문제)
• 1등은 무조건 뽑힌다. 따라서 각 분야의 1등을 기준으로 놓고 비교해주면 된다.
• 성적을 정렬 기준으로 놓고, 성적이 동일하면 면접순위가 높은 사람을 뽑는다.