[백준 - Python] 1946. 신입사원 (그리디)

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

1946번: 신입 사원

 

코드

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(input())
    score = []
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        score.append((a, b))
    _score = sorted(score)

    cnt = 1
    second = _score[0][1]
    for i in range(1, n):
        if _score[i][1] < second:
            cnt += 1
            second = _score[i][1]

    print(cnt)

 

어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해

서류 심사 결과와 면접 성적 중, 적어도 하나가 떨어진다면

A는 결코 선발되지 않는다는 선발 원칙을 바탕으로

회사가 선발할 수 있는 신입사원의 최대 인원을 구하는 문제였다.

 

문제의 아이디어는 비슷하게 떠올렸으니 구현을 복잡하게 끌어가다 끝내 통과를 못했다.

다른 분들의 풀이를 참고했다.

 

서류 심사 성적으로 오름차순 정렬된 리스트에서

면접 성적 비교를 통해 채용 여부를 결정하는 방식으로 구현했다.

 

여기서 헷갈리면 안 되는 것은 

점수가 아니라 등수로 주어지기 때문에

숫자가 작을수록 우수한 성적을 갖고 잇는 것이다.

 

(서류 등수, 면접 등수)로 이루어진 score 리스트를

먼저 서류 등수 기준으로 오름 차순 정렬한다.

이로서 리스트의 가장 앞에 있는 사람은 서류로 모든 사람 중 1등인 사람이 된다.

 

서류가 1등인 사람의 면접 등수를 기준으로 이후 사람들의 면접 등수와 비교하여,

면접 등수가 높다면, 즉 숫자가 작다면

선발 가능한 사람이므로 카운팅 변수인 cnt를 하나 증가시킨다.

 

그리고 여태 지나왔던 지원자들의 면접 시험 성적 중

가장 좋은 등수가 있으면 second에 저장해준다.

이렇게 하면 그 이후로 특정 지원자 i의 면접 시험 성적과  second만 비교하여

특정 지원자 i 가 선발 될지 안 될지 파악할 수 있다.

 

 

정리

서류나 면접 중 1등은 무조건 합격하고

그 외의 사람들은 합격자의 서류나 면접 성적 중 1개라도 높으면 선발된다는 선발 규칙을 갖는다.

 

우선 서류 성적을 기준으로 정렬을 하여 가장 첫 번째 지원자는 서류 1등으로 합격을 시키고

이 서류 1등으로 합격한 합격자의 면접 성적과 나머지 뒤의 사람들을 비교를 하는데,

이미 나머지 사람들은 합격자보다 서류에서 등수가 낮은 사람이기 때문에

면접 성적이 합격자보다 우수해야 선발된다.

 

면접 성적이 우수할 경우 카운팅을 해주고

합격자 면접 성적 기준점을 업데이트 해준다.