9. 백준 1946번: 신입 사원 문제풀이

백준 1946번: 신입사원 (https://www.acmicpc.net/problem/1946)

 

문제의 핵심

1.다른 모든 지원자와 비교했을 때 적어도 하나라도 다른 지원자보다 등수가 높아야한다.

->1차 시험 등수를 기준으로 오름차순 정렬 시킨다.

->정렬된 등수대로 2차 시험 등수를 비교한다.(1차 시험에서 자기 보다 등수가 높은 사람보다  2차 등수가 높아야만 뽑힐 수 있다.)

위 그림과 같이 1차 시험 등수로 오름차순 정렬 시킨 후 2차 시험등수를 비교 해가면 (1,4), (2,3), (3,2), (4,1) 총

네 명의 신입사원이 나오고

두번째 케이스에서는 (1,4), (4,2), (6,1) 로 세 명의 신입사원이 나온다.

 

import sys

def recruit():
    T = int(input())
    for i in range(T):
        N = int(input())
        arr = []
        for j in range(N):
            a, b = map(int, sys.stdin.readline().split())
            arr.append((a, b))

        arr.sort()
        cnt = 0
        aMax = 100001
        bMax = 100001
        
        for i in arr:
            if i[0] < aMax and i[1] > bMax:
                cnt += 1
                aMax = i[0]
            elif i[0] > aMax and i[1] < bMax:
                cnt += 1
                bMax = i[1]
            elif i[0] < aMax and i[1] < bMax:
                cnt += 1
                aMax = i[0]
                bMax = i[1]
        print(cnt)

recruit()