[백준] q1946 신입 사원

문제

주어진 각 테스트 케이스에 대해서 문제에서 주어진 규칙에 맞게 선발할 수 있는 신입사원의 최대 인원수를 출력하라.

어떻게 풀 것인가?

• 슈도코드
  1. 지원자의 서류심사 성적을 기준으로 오름차순 정렬한다.
  2. 서류심사 성적이 제일 좋은 지원자는 신입사원으로 선발한다.
  3. 서류심사 성적이 제일 좋은 지원자의 면접시험 성적을 변수 m에 저장한다.
  4. 서류심사 성적이 좋은 순서대로 면접시험 성적을 비교한다.
  5. 면접시험 성적이 더 좋은 지원자의 면접시험 성적을 변수 m에 저장한다.
  6. 해당 지원자를 신입사원으로 선발한다.
  7. 4~6 과정을 반복한다.
  8. 모든 지원자를 다 검토했다면, 신입사원의 수를 출력한다.
• 해설

서류심사 성적이 제일 좋은 지원자 A는 신입사원으로 선발된다.

지원자 B가 신입사원으로 선발되려면, 지원자 A보다 면접시험 성적이 좋아야만 한다. 지원자 B의 면접시험 성적이 더 좋다면, 신입사원으로 선발한다.

지원자 B보다 서류심사 성적이 좋지 않은 지원자 C가 신입사원이 되려면, 지원자 A와 B보다 면접시험 성적이 더 좋아야만 한다. 단, 지원자 B의 서류심사 성적은 지원자 A보다 높기 때문에 지원자 A와의 성적 비교는 불필요하다. 따라서 지원자 B보다 서류심사 성적이 좋다면, 지원자 C를 신입사원으로 선발한다.

매 순간 가장 적합한 신입사원을 선택한다는 점에서 그리디 알고리즘으로 해결해야 하는 문제라고 생각한다.

import sys
# 테스트 케이스의 개수 T 입력받기
t = int(input())
for _ in range(t):
    n = int(input())  # 지원자의 숫자 N 입력받기
    candidate = []
    for _ in range(n):
        candidate.append(list(map(int, sys.stdin.readline().rstrip().split())))  # 지원자의 서류심사 성적, 면접 성적의 순위 입력받기

    candidate.sort()  # 첫 번째 원소로 오름차순 정렬하기

    cnt = 1
    m = candidate[0][1]

    for a in candidate:
        if m > a[1]:
            m = a[1]
            cnt += 1
    print(cnt)

• 시간 복잡도

지원자의 숫자 N의 범위가 1 ≤ N ≤ 100,000 이다. 따라서 프로그램의 시간 복잡도가 O(N^2)이 되면 안된다.

위 알고리즘의 시간 복잡도는 O(NlogN) 이다. 왜냐하면 sort() 메소드를 사용했기 때문이다.

추가적으로 input() 대신 sys.stdin.readlin()을 이용하여 입력을 받는데 소요되는 시간을 줄여준다.