[코딩테스트] 백준 신입사원(실버1)

아이디어

임의의 선발된 a는 임의의 선발된 b보다 서류, 면접 점수 중 하나는 높아야 한다.

→ 나를 제외한 모든 선발된 사람에 대해 조건 충족 필요

• 그리고 그러한 조건을 만족시키는 사람이 최대가 되도록 선발을 해야 한다.

일단 하나의 기준을 잡아보자. 먼저 서류 점수로 정렬을 해보자.

이때, 서류 점수가 낮은 사람은 면접 점수가 높아야만 선발 가능하다. 이렇게 최대 명수를 구해야 한다.

예를 들어,

14 (A)

25

36

42 (B)

57

61 (C)

73 (D)

이렇게 정렬했다고 가정하면, 첫번째 사람은 서류 점수가 가장 작기 때문에 면접 점수가 다른 사람들보다 높아야만한다. 따라서 본인보다 면접 점수가 낮은 사람만 함께 뽑힐 수 있다.

이렇게 뽑았다고 가정하면, 문제가 생긴다. 뽑힌 A를 제외한 B,C,D끼리 조건을 만족시키지 못한다. 이때 조건을 만족시키지 못하는 이유는 B,C보다 D의 서류점수가 이미 높은데, D의 면접 점수도 B,C보다 높기 때문이다. 위의 조건들에 따라서 오른쪽 면접 점수는 A를 기준으로 내림차순으로 정렬되어야 한다는 것을 알 수 있다.

그리하여 A부터 아래로 내려오면서 한명씩 기준으로 잡고, 본인보다 면접 점수가 낮은 사람의 수를 센다. 그리고 그 값들을 배열에 담고, 가장 많은 수의 사람을 출력한다.

import sys

t = int(sys.stdin.readline())
answer = []
for i in range(t):
  n = int(sys.stdin.readline())
  candidates = []
  for k in range(n):
    candidates.append(list(map(int, sys.stdin.readline().rstrip().split())))
  candidates.sort(key=lambda x: x[0])
  counts = []

  for c in range(0, len(candidates) - 1):
    count = 1
    now = candidates[c][1]
    for d in range(c + 1, len(candidates)):
      if now > candidates[d][1]:
        count += 1
        now = candidates[d][1]
    counts.append(count)

  answer.append(max(counts))

for a in answer:
  print(a)

하지만 어떻게 고쳐도 시간초과 …

시간복잡도 계산

시간제한은 2초, 입력은 최대 2,000,000(이백만)개이다. 파이썬 기준 2초에 4000만번 연산 가능한데, n제곱은 무조건 4천만번을 넘고, log2(이백만),약20 * 이백만 = 40,000,000(4천만)이기 때문에, 딱 nlogn까지만 연산 가능하다.

구글링 참고하여 고친 코드

비교하여 모든 카운트를 배열에 담는 것이 아니라, 가장 서류 점수가 낮은 사람의 면접 점수를 기준으로 그 사람보다 면접점수가 낮은 사람의 수를 세기만 하면 된다!

import sys
t = int(sys.stdin.readline())
answer = []

for i in range(t):
  n = int(sys.stdin.readline())
  candidates = []
  for k in range(n):
    temp = list(map(int, sys.stdin.readline().rstrip().split()))
    candidates.append(temp)

  candidates.sort()
  count = 1
  now = candidates[0][1]
  
  for c in range(1,n):
      if now > candidates[c][1]:
        count += 1
        now = candidates[c][1]

  print(count)