[백준 1946 파이썬] 신입 사원 (실버1, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : △

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())
    rank = [list(map(int, input().split())) for _ in range(N)]
    rank_asc = sorted(rank)
    top = 0
    result = 1
    
    for i in range(1, len(rank_asc)):
        if rank_asc[i][1] < rank_asc[top][1]:
            top = i
            result += 1
    
    print(result)

풀이 요약

1. 서류 심사 결과로 성적을 오름차순 정렬한다.

2. 1 4
   2 3
   3 2
   4 1
   5 5

   이제 첫 번째 사람부터 쭉 for 돌면서 채용 사람 수를 카운팅할 것이다.

   일단 세 번째 사람의 성적을 보자. 그 밑에 있는 사람들과 비교했을 때, 서류 심사 성적이 반드시 세 번째 사람이 높으므로, 경쟁에서 이긴다. 따라서, i번째 사람에 대해, 그 이전의 사람들인 0~(i-1)번째 사람들과 면접 심사 결과를 비교하면 i번째 사람이 채용인지 아닌지 결정할 수 있다.

   i번째 사람의 면접 성적이 0~(i-1)번째 사람들의 모든 면접 성적보다 순위가 높으면 이 사람은 채용이다.

   그런데 이렇게 이전의 사람들의 면접 결과를 일일히 for 돌면서 비교하면, N이 최대 10만이므로, 1+2+3+...+100000=5억 정도. 시간 초과된다.

   그러니, 이전 사람들 중에서 면접 성적 순위가 가장 높은 사람의 순위랑만 비교를 하자. 만약 더 순위가 높다면, 그러면 자연스레 이전 사람들 모두보다 순위가 높은게 된다.

3. 이전 사람들 중 가장 높은 면접 순위를 top이라고 하자.

   일단 첫 번째 사람은 무조건 채용이니까, result에 1을 할당해두고, top=첫번째 사람 면접 순위이다.

   그리고 두 번째부터 for를 돌면서, 만약 현재 사람의 면접 순위가 top보다 값이 작으면(순위가 높으면), result에 1을 더하고 top을 현재 면접 순위 값으로 갱신한다. 그러면 첫 번째부터 현재까지의 사람들 중 가장 높은 면접 순위를 갱신한게 된다.

   이 흐름으로 끝까지 진행하고 result를 출력하면 된다.

배운 점, 어려웠던 점

• 면접 순위를 비교하는 부분에서, 좀 더 효율적으로 시간복잡도를 줄이는 방식을 생각해내지 못했다. 현재에 대해, 이전 사람들 for를 역방향으로 돌면서 자신보다 순위가 낮고, 그 사람이 채용이면 for 탈출하고 현재 사람도 채용인걸로 판별하는 코드를 썼다가 통과는 했는데, 다른 사람 풀이보고 더 깔끔하게 코드를 최적화했다.