[백준] 1946 파이썬(python) : 신입 사원 - (★)

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

1946번: 신입 사원

 

 

서류 점수 순위와 면접 점수 순위 2개를 같이 비교하는 반복문을 만들면 O(n^2)의 복잡도가 나오는데 시간초과가 걸린다.

 

import sys
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    rank = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
    rank.sort() #1
    top, res = 0, 1 #2
    for i in range(1, len(rank)): #3
        if rank[i][1] < rank[top][1]: #4
            top = i
            res += 1
    print(res)

 

#1 : 서류점수 순위 기준으로 정렬

#2 : 첫번째 사람의 인덱스는 0이므로 top은 0으로 그리고 합격한 사람의 수는 1로 초기화

#3 : 두번째 사람의 인덱스(1)부터 마지막 인원까지 반복

#4 : 자신보다 서류점수 순위가 앞선 사람 중에서 면접 점수 순위가 가장 높은 사람과의 비교

면접점수 순위가 내가 더 높다면 채용이고 top을 갱신

 

테스트 케이스의 두번째 예시를 정렬하면 다음과 같다.

(1 4) (2 5) (3 6) (4 2) (5 7) (6 1) (7 3)

여기서 뽑히는 인원은 3명이라고 한다.

 

서류점수 순위 기준으로 정렬했기 때문에 첫번째 사람은 무조건 뽑힌다. 그 뒤에 있는 사람들은 자신의 앞의 사람보다 서류점수 순위에서 낮으니 면접점수 순위에서 앞사람들보다 높아야 채용이 된다. 하지만 앞에 있는 사람들 모두의 면점점수 순위와 비교할 수는 없다. 시간복잡도가 O(N^2)가 되기 때문이다. 그러니 앞사람 중 면접점수 순위가 가장 높은 사람이랑 비교해서 더 높으면 앞선 사람모두에게 높은것이 되므로 한번만 비교를 하면 된다.

 

그리디는 어렵다. 사실 아직도 탐욕스러운 알고리즘이 무엇을 뜻하는지 잘 모르겠다.

 

---

참고한 블로그