BOJ(백준) 1946[신입 사원]

안녕하세요! 오늘은 백준의 1946번 문제인 “신입 사원” 문제를 함께 풀어보겠습니다. 이 문제는 여러 명의 지원자 중에서 서류 심사와 면접 순위를 기반으로 신입 사원을 선발하는 문제입니다. 함께 문제를 해결해보도록 하죠!

 

1. 문제 설명

1) 여러 명의 지원자가 있습니다. 각 지원자는 서류 심사 순위와 면접 순위가 매겨져 있습니다.

2) 두 순위 중 하나라도 다른 지원자보다 높으면 그 지원자는 선발될 수 없습니다.

3) 이러한 조건 하에서 최대한 많은 신입 사원을 선발하려 합니다.

 

문제 URL: https://www.acmicpc.net/problem/1946

 

2. 접근법

1) 입력받기: 테스트 케이스 수와 각 테스트 케이스별 지원자의 서류 및 면접 순위 정보를 입력받습니다.

2) 정렬: 서류 심사 순위를 기준으로 지원자들을 정렬합니다.

3) 선발 기준 설정: 서류 심사 순위가 높은 지원자부터 면접 순위를 비교하여 신입 사원을 선발합니다.

4) 결과 출력: 각 테스트 케이스별로 선발된 신입 사원의 수를 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

ans = []
T = int(input())        # 테스트 케이스의 수를 입력 받음
for _ in range(T):
    N = int(input())    # 각 테스트 케이스의 지원자 수를 입력 받음
    arr = []
    for _ in range(N):
        # 각 지원자의 서류 심사 순위와 면접 순위를 입력 받아 리스트에 추가
        arr.append(list(map(int, input().split())))
    arr.sort()  # 서류 심사 순위를 기준으로 오름차순 정렬

    cnt = 1             # 첫 번째 지원자는 무조건 선발
    rank = arr[0][1]    # 첫 번째 지원자의 면접 순위를 저장

    for i in range(1, N):   # 두 번째 지원자부터 반복
        vsNum = arr[i][1]   # 현재 지원자의 면접 순위
        if vsNum < rank:    # 현재 지원자의 면접 순위가 기존의 최소 면접 순위보다 낮으면
            cnt += 1        # 선발 인원 증가
            rank = vsNum    # 최소 면접 순위를 현재 지원자의 면접 순위로 갱신

    ans.append(cnt)         # 각 테스트 케이스의 결과를 리스트에 추가

for i in range(T):
    print(ans[i])  # 각 테스트 케이스의 결과 출력

 

4. 코드 설명

1) 입력받는 부분

• T를 입력받아 테스트 케이스 수를 설정합니다.

• 각 테스트 케이스마다 N을 입력받아 지원자의 수를 설정하고, 지원자들의 서류 심사 순위와 면접 순위를 입력받아 리스트에 저장합니다.

2) 정렬:

• 입력받은 지원자 리스트를 서류 심사 순위를 기준으로 오름차순 정렬합니다.

3) 선발 기준 설정

• 첫 번째 지원자는 무조건 선발합니다.

• 첫 번째 지원자의 면접 순위를 기준으로 이후 지원자들의 면접 순위를 비교하여 선발 여부를 결정합니다.

• 만약 현재 지원자의 면접 순위가 기존의 최소 면접 순위보다 낮다면, 해당 지원자를 선발하고 최소 면접 순위를 갱신합니다.

4) 결과 출력

• 각 테스트 케이스의 결과를 리스트에 추가하고, 이를 출력합니다.

5. Github으로 확인

coTest/BOJ/BOJ01_05_04_1946.py at main · pcy4196/coTest