[이진탐색]- 씨름선수(그리디)

씨름선수(그리디)

 

현수는 씨름 감독입니다.

현수는 씨름 선수를 선발공고를 냈고, 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())
arr=[]

for i in range(n):
    arr.append(list(map(int,input().split())))

arr.sort(key = lambda x:-x[0])

cnt=1
for i in range(1,n):
    for j in range(i-1,-1,-1):
        Flag=0
        if arr[i][1]<=arr[j][1]:
            Flag=1
            break
        else:
            continue
    if Flag==0:
        cnt+=1

print(cnt)

몸무게와 키중 적어도 하나는 커야 하므로 우선 몸무게로 내림차순으로 정렬한뒤  키가 가장큰 한명을 카운팅한다.

그 후 이제 몸무게만 비교하면 된다.

왜냐 ? 이미 키 순으로 정렬이 되있기 때문에 탐색하는 인덱스 선수의 앞 인덱스 선수들의 몸무게와 비교하여 위의 모든 선수들보다 몸무게가 크면 카운팅하면된다. 

 

 

정답코드

 

 

import sys
sys.stdin=open("input.txt", "r")
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)

나와 똑같은 접근의 로직이지만 카운팅하는 로직이 다르다.

해당 문제는 키순으로 정렬한 뒤 몸무게를 탐색하며 가능 큰 값이 나올때마다 큰값을 갱신하며 카운팅을 하면 끝이기도 하다 !