[백준] 1946번 신입 사원 - 파이썬

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

1946번: 신입 사원

 

풀이

신입사원으로 입사하기 위해서는 서류 성적, 면접 성적 둘 중에 하나라도 다른지원자한테 지면 안된다.

적어도 하나는 다른 지원자를 이겨야 신입사원이 될 수 있다. 고로 서류심사 성적으로 정렬해준 뒤 면접 성적으로 비교를 해준다. 서류심사 성적이 낮은 지원자는 자신보다 높은 서류심사 성적을 가진 지원자의 면접 성적을 앞서야한다.

서류심사 성적 순으로 정렬하기 위해 .sort( )를 써주었다. 그 이후에 max로 현재 지원자(for 문의 i가 현재지원자의 인덱스)보다 높은 서류심사 성적을 가지고 있는 사람들 중 가장 낮은 면접 심사 성적이라 비교해서 성적이 더 높으면 신입사원으로 입사가 가능하다.

 

# 1946 신입사원
# T = 테스트 케이스, N = 인원 수
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    li = []
    answer = 1

    for i in range(N):
        li.append(list(map(int, input().split())))

    # o(n^3) 계산 막기 위해 sort로 서류순위부터 계산
    li.sort()
    max = li[0][1]
    for i in range(1, N):
        # 적어도 하나는 다른 지원자를 이겨야 하기에 면접순위에서 가장 낮은 지원자와 순위 비교
        if li[i][1] < max:
            answer += 1
            max = li[i][1]
    
    print(answer)