6. 씨름선수 (그리디)

[문제 아이디어]

이중 for 문 돌리면 비효율적이다.

 

for 문을 이용한 tuple 형태로 변수 저장하기

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

 

 

*변수 한 번에 바꾸기

 ctrl + shift + alt + 'j' 

 

[ 문제 씨름선수 (그리디) ]

현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, 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
sys.stdin = open("input.txt", "rt")

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

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

players.sort(reverse = True)

largest = 0
cnt = 0
for x, y in players:
    if y > largest:
        largest = y
        cnt += 1
print(cnt)

 

이중 for 문

n = int(input())
players = [list(map(int, input().split())) for _ in range(n)]

players.sort()

cnt = 0  # 탈락 인원
for i in range(n):
    for j in range(i+1, n):
        if players[i][1] < players[j][1]:
            cnt += 1
            break

print(n-cnt)

 

*본 문제는 인프런 김태원 강사님의 파이썬 알고리즘 문제풀이 강의에 기반합니다.