씨름 선수(그리디) - python

<문제>

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, 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())
L=[]
for i in range(n):
    h, w =map(int,input().split())
    L.append((h,w))
cnt=0
for x,y in L:
    #print("x = {}".format(x))
    check_value = 0
    for i in range(n):
        if x < L[i][0] and y < L[i][1]:
            break
    else:
        cnt+=1
        
print(cnt)

# 정렬 후 검사하는게 좀 더 빠른거 같다
# 키로 정렬 후 몸무게 만 비교를 해서 하면 반복문 한번에 가능하다 O(N)에 가능

# 정렬 후 검사하는게 좀 더 빠른거 같다
# 키로 정렬 후 몸무게 만 비교를 해서 하면 반복문 한번에 가능하다 O(N)에 가능
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)