백준 1946번 - 신입 사원

어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

# 틀린 코드

문제 해석부터 해보자. 어떤 A의 성적이 다른 모든 지원자의 2가지 성적보다 떨어진다면 선발되지 않는다. 그래서 반복문을 이용해 모든 지원자의 성적을 돌면서 2개의 성적을 비교하였다.
같은 지원자와 비교하지 않기 위해 i+1번째부터 이중 for문을 돌았고 정렬을 하면 좀 더 빨리 탐색할 수 있을 거라고 생각하여 정렬하였다.

그 결과 시간초과가 났다. 사실 이중 for문을 썼을 때 시간초과가 날 거라고 예상은 했다. 입력때문에 쌓인 for문을 생각하면 반복이 끝도 없다. 바꿀 수 있는 부분은 탐색할 때 사용한 이중 for문밖에 없다. 하지만 전체 지원자를 비교해야 되는데 어떻게 for문을 안 돌 수 있을까?

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
  N = int(input())
  count = 0
  applicant = []
  for _ in range(N):
    a, b = map(int, input().split())
    applicant.append((a, b))
  
  applicant.sort(reverse=True)

  for i in range(len(applicant)):
    for j in range(i+1, len(applicant)):
      if applicant[i][0] > applicant[j][0] and applicant[i][1] > applicant[j][1]:
          count += 1
          break
  print(N - count)

# 정답 코드

정답은 정렬을 통해 알아낼 수 있었다. 등수는 중복없이 매겨져 있고 정렬을 할 경우 서류점수 1등부터 꼴등까지 줄세운다. 꼭 모든 지원자를 확인할 필요가 없다는 부분이 포인트다.

예를 들어 서류점수 3등인 사람이 있다. 이 사람은 서류점수 1,2등인 사람보다 떨어진다. 합격하려면 면접점수가 1등과 2등 두명의 점수보다 높아야한다. 근데 모두 체크하는 게 아니라 더 높은 점수만 기억해서 그 점수랑 비교하는 것이다. 그 점수보다 높으면 두명보다 높은 점수를 얻은 것이니까 합격할 수 있다.

이러한 원리로 최고 점수, 즉 등수가 가장 높은 점수를 저장해 다른 지원자와 비교하여 for문을 돌지 않아도 합격자를 가릴 수 있다.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
  N = int(input())
  count = 0
  applicant = []
  for _ in range(N):
    a, b = map(int, input().split())
    applicant.append((a, b))
  
  applicant.sort()
  
  minRank = applicant[0][1]
  for i in range(len(applicant)):
    if minRank > applicant[i][1]:
      minRank = applicant[i][1]
    if minRank < applicant[i][1]:
      count += 1
  print(N - count)