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