[파이썬 알고리즘 문제풀이] - Section4 / 이분탐색(결정알고리즘) & 그리디 알고리즘 - 6

🎈 씨름 선수(그리디)

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습 니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했습니다.”
만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다.

▣ 입력설명
첫째 줄에 지원자의 수 N(5<=N<=50)이 주어집니다.
두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두 다릅니다.

▣ 출력설명
첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요.

▣ 입력예제 1
5
172 67
183 65
180 70
170 72
181 60

▣ 출력예제 1
3

import sys
sys.stdin = open("input.text", "rt")

N = int(input())
data = list()

for i in range(N):
    a,b = map(int, input().split())
    data.append((a,b))  #키, 몸무게

cnt = 0 #뽑히는 최대 인원
max_m = -24242424
data.sort(reverse = True)  #키로 내림차순 그렇다면 몸무게만 비교하면 해결된다. 이렇게 생각할 수 있어야.
for i in range(N):
    if data[i][1] > max_m:
        cnt += 1
        max_m = data[i][1]

print(cnt)

🎃 코멘트
두 개를 모두 비교해야 한다고 생각이 든다면 하나는 조건 하나는 미리 정렬해 놓고 다른 하나로 비교를 하자. 또한 반복문을 효율적으로 쓸 수 있게 아이디어 생각했으면 됐다.