🟩 [백준] [Python] 1946번_신입 사원

문제

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

1946번: 신입 사원

풀이

# 백준 1946번 문제 - 신입 사원
from collections import deque
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    arr = []
    for _ in range(n):
        a, b = map(int, input().split())
        arr.append((a,b))
    arr.sort(key = lambda x: x[0])

    res = arr[0][1]
    cnt = 1 # 첫번째는 무조건 사원으로 뽑히기 때문에 1부터 시작
    for compare in arr:
        if res > compare[1]:
            cnt += 1
            res = compare[1]
    print(cnt)

처음에 아무 생각없이 res = min(res, compare[1])  을 적용했다가 시간초과가 발생하였다. 

min은 시간복잡도가 O(n)인데 for문 안에 있어서 시간복잡도가 O(n^2)으로 늘어난 것이다. 

그래서 코드를 바꿔줬는데 그래도 시간초과가 발생하여 성적을 입력받을 때 sys를 사용하여 해결하였다.