소스코드

import sys
input = sys.stdin.readline

T = int(input().strip())
results = []
for _ in range(T):
	N = int(input().strip())
	result = 1 # 각 테스트 케이스의 결과 : 첫번째 사람은 무조건 합격
	
	applicants = []
	for _ in range(N):
		first, second = map(int, input().strip().split())
		applicants.append((first,second))
		
	# 정렬 : 서류심사 성적순
	applicants.sort(key=lambda x: x[0])
	
	# 순차순회
	min_rank = applicants[0][1]
	for i in range(1,N):
		first, second = applicants[i]
		
		# 현재 등수보다 더 앞 등수가 있는 경우
		if second < min_rank:
			min_rank = second
			result += 1
			
	results.append(result)
	
print('\\n'.join(map(str, results)) + '\\n')

풀이

• 2가지 평가 기준 중 하나라도 다른 지원자보다 떨어지면 선발이 안되므로, 어느 한 기준에서 우위를 점하지 못하면 나머지에서 반드시 앞서야 합니다.
• 한 쪽을 먼저 정렬시켜두고 나머지를 판단해보자는 생각을 했습니다.
  • 서류 점수를 기준으로 정렬해두고, 면접 점수 순위를 이용해서 맨 앞 사람보다 등수가 낮으면 탈락이라고 생각했습니다. 근데 경우의 수를 따져나가다보니 순차탐색을 하던 중에 더 작은 값을 만났을 때, 해당 등수의 뒷 사람은 그 등수보다 더 높아야하더라구요.
  • 브루트포스(완전탐색)의 경우에는 O(N^2)이므로 시간초과입니다. 한 명이 나머지 모두를 비교해야하는 이중탐색문을 작성해야하기 때문입니다.
• 여러 조건을 만족해야할 때, 하나를 정렬해두고 나머지 기준만을 이용해 비교하는 패턴의 문제입니다. 이런 문제를 그리디의 대표적인 하나 고정, 하나 비교 유형이라고 하네요.