[백준] 1946 - 신입 사원 [Python(파이썬)]

문제

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

1946번: 신입 사원

 

풀이

그리디 알고리즘 문제였다. n이 최대 100,000이므로 관건은 O(nlogn) 안에 풀어야 한다는 것이었는데, 이 문제의 경우 O(n) 안에 풀이가 가능했다. "첫 번째 점수인 서류심사 성적순으로 정렬을 하고, 두 번째 점수인 면접 성적을 비교해서 합격자를 결정하면 된다."라는 기본적인 아이디어는 모두 비슷할 것이다. 하지만 두 번째 점수인 면접 성적을 비교하는 부분이 다소 까다로웠다.

 

여기서 생각의 전환이 필요하다. 판별을 하는 면접자를 A라고 지칭할 때, "자신보다 서류심사 성적이 높은 면접자들의 면접 성적보다 A의 성적이 높아야 한다."를 "자신보다 서류심사 성적이 높은 면접자들의 면접 성적 중 가장 높은 성적보다 A의 성적이 높아야 한다." 이렇게 바꿔서 생각해볼 수 있다.

 

이에 따라 가장 높은 면접 성적만을 기록하면서 비교하는 방식으로 합격자를 선택할 수 있다. 예를 들어, 만약 현재 판별하고자 하는 이 가장 높은 면접 성적보다 높으면(rank < min_rank) A를 선택(cnt += 1)하고 면접 성적을 업데이트하면 된다.

 

코드

import sys

t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    workers = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]
    workers.sort()
    min_rank = workers[0][1]
    cnt = 1
    for i in range(n):
        rank = workers[i][1]
        if rank < min_rank:
            min_rank = rank
            cnt += 1
    print(cnt)