신입 사원 실버 1 (백준, 그리디)

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

1946번: 신입 사원

 

import sys


input = sys.stdin.readline
for _ in range(int(input())):
  people = []
  for _ in range(int(input())):
    s1, s2 = map(int, input().split())
    people.append([s1,s2])
  people.sort(key = lambda x : x[0])
  man = people[0][1]
  ans = 1
  for i in range(1, len(people)):
    if man > people[i][1]:      
      man = people[i][1]
      ans += 1
  print(ans)

처음에는 그냥 정렬한 후 첫 번째 값의 두번째 요소보다 낮은 게 존재한다면 추가를 했는데,

 

그게 아니라 해당하는 값(랭크가 높은, 즉 값이 작은 것)이 나오면 비교 값을 해당 요소로 변경해준다.

 

그 이유는 어차피 정렬된 요소이니 각 요소의 첫번째를 제외한 두번째 값을 비교하고, 조건을 만족하는 값으로 man을 변경 후 비교해주면 전에 비교한 값(초기 값)을 이후에 비교할 필요가 없고, 변경된 값은 초기 값보다 랭크가 높은 것으로 초기화 됐기 때문에 이후의 값들 또한 변경된 값보다 랭크가 높아야만 통과가 가능하기 때문이다.

 

위 말이 이해가 안 간다면 우리는 첫번째 요소로 정렬을 했기에 애초에 순서대로 1,2,3,4...n으로 랭크가 내려간다. 만약 1,7랭크이고 다음 값이 2,3이라면 이후 값은 3,2나 3,1이여야지만 문제의 조건을 만족한다.