[백준 1946] 신입사원

💜 문제요약

어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 면접, 서류 둘 다 떨어진다면 A는 떨어뜨린다.

💜 풀이

• 테스트 케이스의 개수 T(1 ≤ T ≤ 20)
• 지원자의 숫자 N(1 ≤ N ≤ 100,000)

가장 먼저 떠오르는 풀이가 $O(N^2)$ 이었는데, $N$이 천억?가까이 가길래 바로 패스.

그래서 적어도 $O(NlogN)$까지는 줄여야 될 것 같았다.

서류, 면접 둘 다를 순위 비교 해야하기 때문에, 일단 한쪽을 정렬시킨다면, 남은 하나만 비교하면 되겠다는 생각이 들었다.

처음에는 바로 전의 면접 랭킹이랑만 비교하면 된다고 생각했는데 자꾸 틀렸다고 했다ㅠㅠ

   정답   내 답
1 5 ⭕    ⭕
2 2 ⭕    ⭕
3 4 
4 3       ⭕
5 1 ⭕    ⭕
output : 3  

만약 이 test case라면 전이랑만 비교했을 때 4 3 이 포함된다.

바로 전이랑 비교하는 방법은 버리고,
일단 서류가 정렬되어 있으니까 면접 점수의 최저값을 찾아서 계속 update해주면 된다.

import sys
input = sys.stdin.readline
t = int(input())

for _ in range(t) :
  n = int(input())
  people = []
  for _ in range(n) :
    resume, meeting = map(int,input().split())
    people.append([resume, meeting])
  
  people.sort()

  # 정렬하고 나면 서류 1등은 언제나 누구보다 서류 점수가 높기 때문에 항상 뽑힌다! 
  # 그래서 초기 count는 1
  count = 1 
  minimum = people[0][1]
  for i in range(1,n) :
    if people[i][1] <= minimum :
      minimum = people[i][1]
      count += 1
  
  print(count)