그리디 알고리즘 : 신입사원(백준 1946번)

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

1946번: 신입 사원

##### 문제 #####
# 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 
# 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 
# 최고만을 지향한다는 기업의 이념에 따라 
# 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
# 그래서 진영 주식회사는 다른 모든 지원자와 비교했을 때 
# 서류심사 성적과 면접시험 성적 중 적어도 하나가
# 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 
# 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 
# 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
# 이러한 조건을 만족시키면서, 
# 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 
# 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

##### 입력 #####
# 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 
# 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 
# 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 
# 공백을 사이에 두고 한 줄에 주어진다. 
# 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

##### 출력 #####
# 각 테스트 케이스에 대해서 
# 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

 

▶ 접근 방법

'서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다'
해당 조건을 충족할 수 있도록 구현하는 것이 관건이었다.

아래 풀이에서는 서류심사 성적을 오름차순으로 정렬하고,
이후 면점시험 성적만을 비교함으로써 상기 조건을 충족할 수 있도록 구현하였다.

 

▶ 풀이 코드

import sys

T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    N = int(sys.stdin.readline().rstrip())
    # 신입사원 테스트 점수를 서류 심사 성적 기준으로 오름차순 정렬한다.
    score_info = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(N)])
    new_employee = [score_info[0]]
    # 테스트 점수를 하나 씩 꺼내보면서
    for i in range(1, N):
        # 면접 접수 순위를 비교하여 new_employee 리스트에 넣어준다.
        if new_employee[-1][1] >= score_info[i][1]:
            new_employee.append(score_info[i])
    print(len(new_employee))

 

▶ 관련 링크

2021.11.27 - [알고리즘] - 그리디 알고리즘(Greedy Algorithm)이란?

2021.11.27 - [알고리즘] - 그리디 알고리즘 : 동전 0(백준 11047번)

2021.11.27 - [알고리즘] - 그리디 알고리즘 : 잃어버린 괄호(백준 1541번)

2021.11.27 - [알고리즘] - 그리디 알고리즘 : 회의실 배정(백준 1931번)