파이썬 알고리즘-27 (탐색, 그리디) 씨름선수

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

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

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

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

▣ 출력예제 1
3

출력설명
(183, 65), (180, 70), (170, 72)가 선발됩니다. (181, 60)은 (183, 65) 때문에 탈락하고, (172, 67)은 (180, 70) 때문에 탈락합니다.

내 코드

n=int(input())
lst=[]
for _ in range(n):
    h,w=map(int, input().split())
    lst.append((h,w))

lst.sort()
cnt=n
for i in range(n):
    for j in range(n):
        if lst[i][0]<lst[j][0] and lst[i][1]<lst[j][1]:
            cnt-=1
            break
            
print(cnt)

이렇게 하면 시간복잡도가 커져서 안됨

풀이

n=int(input())
body=[]
for i in range(n):
    a, b=map(int, input().split())
    body.append((a, b))
body.sort(reverse=True)
largest=0
cnt=0
for x, y in body:
    if y>largest:
        largest=y
        cnt+=1
print(cnt)

반성점

• 어떻게 저렇게 비교한다는 생각이 떠오르는지 모르겠다. 나는 뇌가 없는건가

배운 것

• 두 개의 다른 항목을 비교하여 하나라도 큰 것을 찾을 때: 하나를 기준으로 내림차순으로 정렬하고 다른 하나는 서로 비교하여 가장 큰 값이 되면 하나라도 큰 것.