[Python] BOJ/백준 1946번 신입 사원

[문제]

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

1946번: 신입 사원

 

[풀이]

우선.. for문을 두 번 쓰면 런타임 에러가 난다. 당연함. 100,000명을 2차 반복문으로 돌리면.. 

따라서 반복문 한번에 비교를 끝내야한다.

그러기 위해 우선 첫 번째 점수를 기준으로 정렬을 한 후에 rank_asc 변수에 담는다.

 

rank_asc 변수의 첫 번째 원소는 서류 심사가 가장 높은 사람이 오기 때문에 이 사람의 면접 결과가 몇 점이든 무조건 신입사원으로 선발된다. 그렇기 때문에 result는 1로 초기화하고 top에 첫 번째 사람을 담는다.

 

두 번째 사람부터 반복문을 돌면서 첫 번째 사람의 면접 순위보다 현재 차례 사람의 순위가 더 높으면(rank_asc[i][1] < rank_asc[top][1]) result에 1을 더하고 top에 현재 사람을 넣는다.

이렇게 끝까지 반복문을 돌고 result를 출려하면 된다.

 

 

[코드]

import sys

for _ in range(int(sys.stdin.readline())):
    N = int(sys.stdin.readline())
    rank = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    rank_asc = sorted(rank)
    top, result = 0, 1

    for i in range(1, len(rank)):
        if rank_asc[i][1] < rank_asc[top][1]:
            top = i
            result += 1
    print(result)