📌문제
https://www.acmicpc.net/problem/1946
🎖️난이도
✔️풀이
import sys
input = sys.stdin.readline # 안해주면 시간초과
t = int(input())
for _ in range(t):
n = int(input())
scores = []
for i in range(n):
a, b = map(int, input().split())
scores.append((a, b))
tmp_max = 0
cnt = 0
scores.sort(key = lambda x : x[0]) # 정렬 후 완전 탐색 (tmp_max와 비교)
for i in range(n):
if i == 0 or scores[i][1] < tmp_max:
cnt += 1
tmp_max = scores[i][1]
print(cnt)
🧠노트
우선 통제해야 할 변수가 2가지 (서류점수, 면접점수) 였으므로
각각을 기준으로 한 번씩 정렬하거나, 한 점수(등수)를 기준으로 정렬을 해서 따져봐야겠다는 생각이 먼저 떠올랐다.
우선 서류점수를 기준으로 정렬해보면
서류 점수에 대해서는 정렬이 이미 되어있으니까 (아래로 갈 수록 서류 점수가 낮으므로, 위험!)
아래로 가면서, 면접 점수가 위에 애보다 낮은 등수이면 무조건 탈락이다!
결국 이 문제의 Key Point는,
정렬 & 약간의 그리디! (나만의 기준을 잡아 정렬 후 탈락이 아닌 애 cnt ++)
솔직히 운 좋게 떠올라서 슈루룩 풀린 문제,,^0^
🔍참고
-
'[ 알고리즘 ] > Greedy' 카테고리의 다른 글
[프로그래머스] 단속카메라 (0) | 2022.09.01 |
---|---|
[프로그래머스] 구명보트 (0) | 2022.09.01 |
[백준] 21758. 꿀 따기 (0) | 2022.08.17 |
[백준] 16953. A → B (0) | 2022.08.17 |
[백준] 1541. 잃어버린 괄호 (0) | 2022.06.30 |