[정글 알고리즘] - [중] 백준1946- 신입 사원- 실버1

 

정렬 후 기준값이 어떻게 갱신되는지 눈에 보이도록 만든 상세형 버전이다.

1. 문제를 아주 짧게 말하면

다른 지원자보다 서류와 면접이 모두 밀리는 사람은 선발할 수 없다. 이 조건을 만족하며 최대로 몇 명을 선발할 수 있는지 구하는 문제다. [Source](https://www.acmicpc.net/problem/1946)

2. 핵심 아이디어

한 기준으로 정렬하고 다른 기준만 본다

서류 등수로 정렬하면, 현재 사람보다 앞에 있는 사람들은 모두 서류가 더 좋다. 따라서 현재 사람은 면접 등수만 지금까지의 최솟값보다 좋으면 선발 가능하다.

3. 전체 코드

1import sys

2

3input = sys.stdin.readline

4t = int(input())

5

6for _ in range(t):

7 n = int(input())

8 applicants = [tuple(map(int, input().split())) for _ in range(n)]

9 applicants.sort()

10

11 count = 1

12 best_interview = applicants[0][1]

13

14 for i in range(1, n):

15 interview_rank = applicants[i][1]

16 if interview_rank < best_interview:

17 count += 1

18 best_interview = interview_rank

19

20 print(count)

4. 코드 한 줄씩 설명

줄	코드	설명
3	input = sys.stdin.readline	빠른 입력을 위한 설정이다.
4	t = int(input())	테스트케이스 개수를 입력받는다.
6	for _ in range(t):	현재 테스트케이스의 지원자 수를 입력받는다.
7	n = int(input())	각 지원자의 (서류 등수, 면접 등수)를 입력받는다.
8	applicants = [tuple(map(int, input().split())) for _ in range(n)]	서류 등수 기준 오름차순으로 정렬한다.
10		첫 지원자는 무조건 선발 가능하므로 1명부터 시작한다.
11	count = 1	현재까지 본 사람들 중 가장 좋은 면접 등수를 저장한다.
13		두 번째 지원자부터 끝까지 확인한다.
14	for i in range(1, n):	현재 지원자의 면접 등수를 꺼낸다.
15	interview_rank = applicants[i][1]	현재 면접 등수가 기존 최고보다 더 좋으면 선발 가능하다.
16	if interview_rank < best_interview:	선발 인원을 1 늘린다.
17	count += 1	이 사람의 면접 등수가 새로운 기준이 되므로 갱신한다.
19		최종 선발 가능한 인원 수를 출력한다.

import sys
# input = sys.stdin.readline

5. 예시 흐름 시각화

정렬 후 첫 지원자 (1, 4)

첫 사람은 앞에 비교 대상이 없으므로 일단 선발한다. 현재 최고 면접 등수는 4다.

지원자 (서류 2, 면접 3)

면접 등수 3가 현재 최고 4보다 더 좋으므로 선발

지원자 (서류 3, 면접 2)

면접 등수 2가 현재 최고 3보다 더 좋으므로 선발

지원자 (서류 4, 면접 1)

면접 등수 1가 현재 최고 2보다 더 좋으므로 선발

지원자 (서류 5, 면접 5)

면접 등수 5가 현재 최고 1보다 나쁘므로 탈락

6. 표로 보면 더 쉬운 판정

이해용 예시 지원자들을 서류 기준으로 정렬한 뒤 판정하면 최종 선발 수는 4명이다.

서류 등수	면접 등수	판정 기준
1	4	선발
2	3	선발
3	2	선발
4	1	선발
5	5	탈락

7. 자주 헷갈리는 포인트

• 둘 다 좋아야 선발되는 것이 아니라, 둘 다 밀리지만 않으면 된다.
• 정렬 후 첫 사람은 항상 선발 가능하다.
• 비교 기준은 현재까지의 최선 면접 등수 하나만 유지하면 된다.

8. 복잡도

정렬 때문에 시간 복잡도는 O(N log N) 이다.

추가 순회는 O(N) 이고, 입력 저장 외 추가 공간은 크지 않다.

원문 문제 링크

https://www.acmicpc.net/problem/1946