[Python Algorithm] 그리디 알고리즘 - 씨름 선수

> 이분 탐색(결정알고리즘) & 그리디 알고리즘 (그리디알고리즘 편)

 

📖 문제 : 씨름 선수

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, 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) 때문에 탈락합니다.

 

import sys

n = int(input())
people = []

for i in range(n):
	h, w = map(int, input().split())
	people.append((h,w))
    
people.sort(reverse.True)	# 키가 큰 순서대로 정렬 
largest = 0
cnt = 0
for h, w in people:
    if w>largest:
        largest = w
        cnt += 1
        

print(people)

⭐️ Point ! ⭐️

• 먼저 키로 reverse 정렬을 한 이유는 
  예를 들어,
  172 67
  183 65
  180 70
  170 72
  181 60
  를 정렬하면
  183 65
  181 60
  180 70
  172 67
  170 72
  이렇게 정렬 후, 몸무게만을 두고 본다. 
  첫번째는 무조건 인원으로 추가되고, 두번째 부터는 자기 앞 모든 사람들 보다 몸무게가 커야한다. 
  왜냐하면 키와 몸무게 둘 중에 하나만 커야하는데, 이미 키 순으로 정렬되어있기 때문에
  선택된 사람은 앞(위)에 있는 사람보다 키가 작으므로 몸무게는 무조건 커야하는 것 !
  결국 for문을 2번 돌려 비효율적으로 검사하지말고, 키로 정렬 후,
  몸무게만 두고 봤을 때, max값을 찾듯이 앞에 모든 요소보다 클 경우 카운팅을 해주면 된다.
  
  
• (리스트).sort(reverse=True)

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이