항해99 리부트코스 알고리즘 2주 3일차 백준 1946 신입 사원

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

 

 

 

풀이

 

문제의 핵심은 두 가지 성적 중 하나라도 다른 지원자보다 떨어지면 선발되지 않는다는 점이다

 

• 각 지원자는 두 가지 성적(서류 심사 성적, 면접 성적)을 가지고 있음
• 한 가지 성적이라도 다른 지원자보다 떨어지지 않으면 선발

 

 

문제 해결 전략

1. 정렬: 서류 심사 성적을 기준으로 지원자들을 오름차순으로 정렬
2. 최소 면접 성적 갱신: 서류 심사 성적이 낮은 순서대로 면접 성적을 확인하면서, 현재까지의 최소 면접 성적을 갱신
3. 선발 기준: 현재 면접 성적이 최소 면접 성적보다 좋다면 그 지원자는 선발.

 

예를 들어, 지원자가 5명이고 서류 심사 및 면접 성적이 다음과 같다 (참고로 숫자는 순위임에 유의, 헷갈리지말자)

 

서류 심사                                                                                  성적면접 성적

3	2
1	4
4	1
2	3
5	5

 

이 지원자들을 서류 심사 성적 기준으로 정렬하면 다음과 같음

 

서류 심사                                                                                  성적면접 성적

1	4
2	3
3	2
4	1
5	5

정렬된 상태에서 면접 성적을 기준으로 최소값을 갱신하며 선발 과정을 보면:

1. 첫 번째 지원자 (서류 1, 면접 4) -> 선발, 최소 면접 성적: 4
2. 두 번째 지원자 (서류 2, 면접 3) -> 선발, 최소 면접 성적 갱신: 3
3. 세 번째 지원자 (서류 3, 면접 2) -> 선발, 최소 면접 성적 갱신: 2
4. 네 번째 지원자 (서류 4, 면접 1) -> 선발, 최소 면접 성적 갱신: 1
5. 다섯 번째 지원자 (서류 5, 면접 5) -> 선발 불가 (면접 성적 5가 최소 성적 1보다 나쁨)

최종적으로 선발된 지원자는 4명이다.

 

코드

 

 

 

 

import sys
input = sys.stdin.read

data = input().split()
t = int(data[0])  # 테스트 케이스 수
index = 1

results = []

for _ in range(t):
    n = int(data[index])
    index += 1
    applicants = []

    for i in range(n):
        doc, interview = int(data[index]), int(data[index + 1])
        applicants.append((doc, interview))
        index += 2

    # 서류 성적 기준으로 오름차순 정렬
    applicants.sort()

    # 최소 면접 성적을 현재 최대값으로 초기화
    min_interview = applicants[0][1]
    count = 1  # 첫 번째 지원자는 무조건 선발

    # 두 번째 지원자부터 확인
    for i in range(1, n):
        if applicants[i][1] < min_interview:
            min_interview = applicants[i][1]
            count += 1

    results.append(count)

# 결과 출력
for result in results:
    print(result)

 

• 입력 데이터를 한 번에 읽어와서 필요한 부분을 분리
• 각 테스트 케이스마다 지원자 정보를 서류 심사 성적 기준으로 정렬
• 정렬된 상태에서 최소 면접 성적을 갱신하며 선발할 지원자를 결정
• 각 테스트 케이스의 결과를 저장하고 마지막에 출력