[백준알고리즘] 1946번: 신입 사원 -Python

[백준알고리즘] 1946번: 신입 사원 -Python

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

1946번: 신입 사원

문제 자체도 어려운 편이 아니었는데 계속 시간 초과가 나서 이상했었다.

 

한동안 sys.stdin.readline()대신 input()으로 다뤘더니 생긴 문제였다.

 

입력이 하나의 테스트케이스마다 10만 번 입력이 이뤄질 수 있고, 최대 200만 번의 입력이 이뤄지기 때문에 input()으로는 시간 초과가 발생했던 것이다.

 

문제는 두개의 등수 중 하나의 등수로 오름차순 정렬을 하고 다른 하나의 등수가 자신보다 낮은 사람들 중 최대로 뽑힐 수 있는 사람의 수에 +1을 해주었다.

하나의 등수로 오름차순 정렬을 해주게 되면 순서대로 봤을 때 다른 하나의 등수만 봐서 그 등수가 현재보다 낮은 사람들의 개수를 세면 되기 때문이다.

import sys
for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    score = sorted([tuple(map(int, sys.stdin.readline().split())) for _ in range(n)], key=lambda x:x[0])
    p, ans = n+1, 0
    for s, e in score:
        if p > e:
            ans += 1
            p = e
    sys.stdout.write("{}\n".format(ans))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다