[백준-1946(그리디)] 신입사원
문제
언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
출력
각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.
예제 입력
2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1
예제 출력
4
3
핵심 아이디어 요약
이 문제는 "두 가지 기준(서류 성적, 면접 성적) 중 하나라도 다른 지원자보다 낫지 않으면 탈락"하는 선발 기준을 제시합니다.
이를 효율적으로 처리하기 위해 한 기준(서류)을 기준으로 정렬한 뒤, 나머지 기준(면접 등수)만 비교하는 그리디 전략을 사용합니다.
왜 그리디인가?
- 서류 성적으로 정렬해놓으면 앞에 나오는 지원자는 서류 기준으로는 반드시 뒤의 사람보다 낫거나 같다.
- 따라서 면접 등수만 비교해서 이전보다 더 좋은 사람만 채용하면, 조건을 만족하면서 최대 인원을 뽑을 수 있음.
문제 접근 방법
1. 입력 정리
- 여러 테스트 케이스가 주어짐
- 각 테스트 케이스마다 (서류 등수, 면접 등수) 쌍이 N개 주어짐
2. 정렬 전략
- 서류 등수 기준으로 오름차순 정렬
→ 이후엔 면접 등수만 비교하면 됨.
3. 채용 조건 판단 (그리디 핵심)
- 면접 등수의 최소값(min_Value)을 계속 갱신하면서
- 현재 사람의 면접 등수가 이전 최소값보다 더 좋으면 채용
정리 문장
"서류 기준으로 정렬하고, 면접 성적이 이전보다 더 좋은 경우에만 채용한다"는 아이디어 하나로 이 문제는 효율적으로 풀린다.
두 기준 중 하나라도 모두 못 이기면 탈락이란 조건은, 결국 다른 하나(면접 등수)에 대해 단조 감소 조건만 유지하면 되는 그리디 문제로 환원된다.
import sys # 빠른 입력을 위해 sys 모듈을 불러옴
input = sys.stdin.readline # input() 대신 빠른 입력 함수로 설정
T = int(input()) # 테스트 케이스 개수 입력받기
for _ in range(T): # 테스트 케이스 수만큼 반복
group = int(input()) # 이번 테스트 케이스에서 지원자 수 입력
group_A = [] # 지원자 정보를 저장할 리스트 초기화
for _ in range(group): # 지원자 수만큼 반복하면서
first, last = map(int, input().split()) # 서류, 면접 등수 입력
group_A.append((first, last)) # 튜플로 리스트에 저장
group_A.sort(key=lambda x: x[0]) # 서류 등수 기준으로 오름차순 정렬
min_Value = float('inf') # 면접 등수의 최소값 초기화 (처음엔 무한대로 설정)
count = 0 # 채용된 사람 수를 세기 위한 변수
for first, last in group_A: # 정렬된 지원자 목록을 순회하면서
if last < min_Value: # 현재 면접 등수가 이전 최소보다 좋다면 (숫자가 작다면)
count += 1 # 채용 가능 → count 증가
min_Value = last # 현재 면접 등수를 새로운 기준값으로 설정
print(count) # 해당 테스트 케이스에서 채용된 사람 수 출력