[Python] 1946번 신입 사원

✏️ 문제

 

문제 파악

처음에 문제를 이해한다고 시간을 좀 잡아먹었었다.. 

 

다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

 

이게 무슨 말이냐면 일단 서류나 면접 둘 중에 하나라도 1등인 사람은 다른 어떤 지원자들보다 성적이 높으므로(동석차 없음) 무조건 뽑히게 된다. (한 사람이 두 개 다 1등이면 그 사람만 선발) 

 

그럼 이제 이 1등한 사람을 기준으로 비교하면 되는데 2번째 테스트 케이스를 보면 서류 1등인 사람이 면접 4등인 걸 볼 수 있다. 그럼 면접에서는 이 사람보다 높은 사람이 3명(1등, 2등, 3등)이나 더 있다는 걸 알 수 있는데 차례대로 6 1, 4 2, 7 3 이다. 

이때 7 3은 4 2와 비교했을 때 서류와 면접 둘 다 성적이 떨어진다. 때문에 선발될 수 없으므로 2번째 테스트 케이스에서는 7 3을 제외한 3명이 선발되게 된다.

 

이 부분을 반영한 게 코드에서 조건을 만족하면 변수 cutline의 값이 해당 값으로 변하게 되는 부분이다. 

 

알고리즘

• 그리디 알고리즘
• 정렬

 

 

코드

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

for i in range(t):
  n = int(input())
  applicant = []

  for i in range(n):
    applicant.append(list(map(int, input().split())))

  applicant.sort()
  cutline = applicant[0][1]
  num = 1
  for j in range(1, n):
    if cutline > applicant[j][1]:
      num += 1
      cutline = applicant[j][1]

  print(num)

 

아니 자꾸 시간 초과 뜨길래 뭐가 문제지.. for문 없이 코드 짜야하나 했는데 sys 쓰니까 바로 해결했다.. 이왜진.. sys에 대해 더 찾아봐야겠다..