[BOJ 1946, Python 3] 신입 사원

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

1946번: 신입 사원

 

풀이

N이 작으면 2중 for문으로 풀 수 있겠지만 N = 100,000이미 때문에 2중 for문을 사용하면 시간초과가 나오는 문제입니다.

 

2개를 동시에 비교할 수 있는 logN기법은 모르겠고, for문 하나로 풀 수 있나? 이렇게 생각해보시면 일단 점수중 하나는 순위 순서대로 정렬하는 방법을 떠올리실 겁니다. 이것만 떠올릴 수 있으면 문제는 다 푸신겁니다.

 

편의상 첫 번째 입력값인 서류 심사 성적을 오름차순으로 정렬한다고 해봅시다.

예제 2를 예로 들자면 첫 번째 값을 오름차순으로 정렬했을 때 (1, 4)가 제일 첫 값으로 오는 것을 아실겁니다.

이러면 일단 첫 번째 값을 이길 사람이 없으니 두 번째 값을 이길 수 있는 사람만 찾아야 하는데, 이러면 (?, 1), (?, 2), (?, 3)이 가능하다는 것을 알 수 있습니다.

 

거기다가 첫 번째 값을 오름차순으로 정렬했으니 for문을 돌리면 진행할 수록 첫번째 값의 순위가 낮아진다는 것을 알 수 있죠.

첫 번째 값의 순위가 점점 낮아지므로, 두 번째 값의 순위는 이전에 뽑은 신입 사원의 두 번째 값 순위보다 높은 경우에만 뽑을 수 있게 됩니다.

 

이것도 예시 2번으로 살펴보자면 (?, 1), (?, 2), (?, 3) = (6, 1), (4, 2), (7, 3)이 되는 것을 알 수 있습니다.

오름차순으로 정렬했으므로 (1, 4) -> (4, 2) -> (6, 1) -> (7, 3)으로 확인할텐데 첫 번째 값은 고정시켜 놨으니 뭔 짓을 해도 다음 사원이 이전 사원보다 점수가 높을 수 가 없습니다. 그러므로 두 번째 값으로 이겨야 하는데 (1, 4) -> (4, 2) -> (6, 1) 까지는 괜찮지만  (6, 1) -> (7, 3)에서는 두 번째 값으로 현재 사원이 이전 사원을 이길 수 없으므로 답은 3이 되게 됩니다.

 

이 아이디어로 코드를 짜면 됩니다.

이렇게 하나를 고정 시켜서 푸는 문제는 은근히 많이 보이는 유형의 문제이므로 잘 기억해두시면 좋을 것 같습니다.

 

코드

input = __import__('sys').stdin.readline
for _ in range(int(input())):
    n = int(input())
    arr = sorted([[*map(int, input().split())] for _ in range(n)])
    val = arr[0][1]
    ans = 1
    for i in range(1, n):
        if val > arr[i][1]:
            ans += 1
            val = arr[i][1]
    print(ans)