백준 1946번 파이썬 문제풀이(신입 사원)

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

1946번: 신입 사원

---

정렬 후 도저히 O(N)으로 처리할 방법이 생각이 나지 않아 풀이를 봤다. (후... 이걸 도대체 어떻게 처음부터 생각하는지 ㅠ)

 

풀이 방식은 다음과 같다.

1. 서류점수를 기준으로 오름차순 한다.
2. 서류점수를 기준으로 오름차순 했기 때문에 서류순위는 보장이 되고 면접순위만 비교하면된다.
3. 비교방식은 첫 기준점을 서류점수 1등의 면접순위로 잡아준다.
4. 반복문을 1번 인덱스 부터 돌면서(0번은 서류1등) 첫 기준점인 서류점수 1등의 면접순위보다 
   낮은 순위가 나오면 개수 1개 추가하고 그 순위를 기준으로 잡아준다.
5. 또 뒤로가면서 바뀐 순위를 기준으로 비교하면된다.

import sys

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

for tc in range(T):
    N = int(input())
    freshman = [list(map(int, input().split())) + [i + 1] for i in range(N)]

    freshman.sort(key=lambda x: x[0])

    rank = freshman[0][1]  # 첫 비교대상 면접점수를 저장
    cnt = 1  # 개수를 1로 초기화

    for i in range(1, N):
        if rank > freshman[i][1]:  # 만약 지금 저장된 순위보다 더 작은 순위가 나왔다면
            rank = freshman[i][1]  # 그 순위를 저장하고
            cnt += 1  # 개수 1개 추가

    print(cnt)