2022.02.15 [백준] (python 파이썬) 신입 사원

 

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

1946번: 신입 사원

 

---

풀이

이 문제에서 지원자의 범위가 10만이라서 이중 for문을 쓰면 시간 초과가 발생한다. 그래서 우선 지원자의 순위를 arr에 저장하고 서류 순위로 정렬한다. 그러면 arr[0]의 지원자는 서류는 1등 이므로 무조건 합격한다. arr[0]지원자의 면접순위를 min변수에 대입하고 이와 비교해서 기준의 지원자보다 면접순위가 높으면 합격한다. 이 때 만약 min보다 면접순위가 높으면 min에 대입해준다. 이유는 아래의 지원자는 위의 지원자 보다 서류 순위는 항상 낮기 때문에 면접 순위가 높아야 합격하기 때문이다.

import sys
 
input=sys.stdin.readline
T=int(input())
for _ in range(T):
    arr=[]
    n = int(input())
    cnt=1
    for _ in range(n):
        arr.append(list(map(int,input().split())))
    arr.sort()
    min=arr[0][1]
    for i in range(1,n):
        if min>arr[i][1]:
            min=arr[i][1]
            cnt+=1
    print(cnt)