[백준/python/1946] 신입사원

문제링크 : 신입사원

처음에는 이중 for문을 써서 비교를 해줬더니 시간초과가 났다.
그래서 for문을 하나만 쓰는 방법을 고민하며 풀어줬다.

import sys

t=int(input())
for _ in range(t):
    count=1
    score=[]
    n=int(input())
    for i in range(n):
        paper, interview=map(int, sys.stdin.readline().split())
        score.append([paper,interview])

    score.sort()
    max=score[0][1]

    for i in range(1, n):
        if max>score[i][1]:
            count+=1
            max=score[i][1]

    print(count)

이 문제의 포인트는 두가지 항목 모두가 나보다 높은 사람이 있으면 뽑힐 수 없다는 것이다.

1. 우선 서류를 기준으로 정렬해줬다.
   서류 1위는 무조건 뽑히기 때문에 count를 1로 시작했다.

2. 정렬한 배열에서 인터뷰 순위만 비교해주면 된다.
   배열 2번째 요소는 이미 1번째 요소보다 서류 순위가 낮기 때문에 인터뷰 순위가 더 높아야 합격이다.

3. 만약 인터뷰 순위가 더 높다면, count+1을 해준다. 그리고 다음 요소들은 서류순위가 높은 것들 중에 인터뷰 순위가 가장 높은 것과 비교해주면 되기 때문에 max값을 가장 높은 순위로 바꿔준다.

4. 배열 3번째 요소는 서류에서 이미 1번째, 2번째 보다 낮으므로 인터뷰 순위가 1번째, 2번째보다 높아야한다. 이때, 모든 순위를 비교할 필요 없이 가장 높은 순위랑만 비교하면 되기 때문에 max값과 비교해준다.