[Python-CodingTest] 4-6. 씨름 선수 (그리디 알고리즘)

씨름 선수

문제 정리

입력

5 // n
172 67 // 1번째 선수: 키 몸무게
183 65 // 2번째 선수: 키 몸무게
180 70 // 3번째 선수: 키 몸무게
170 72 // 4번째 선수: 키 몸무게
181 60 // 5(=n)번째 선수: 키 몸무게

처리 과정

1. 선수들의 키와 몸무게를 튜플 형태로 담기
2. 리스트를 (키 기준) 내림차순 정렬
3. 내가 선발되기 위해서는 나보다 앞에 있는 선수(나보다 키가 큰 선수) 모두와 비교해 내 무게가 가장 무거워야 함!
4. 앞에서부터 따졌을 때, 몸무게의 max값을 갱신할 때마다 선발 인원 cnt+=1

출력

3

내 답

import sys
sys.stdin = open("./input/in6.txt", "rt")

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

# player.sort(key = lambda x: (x[1],x[0])) # 몸무게 기준 정렬
player.sort() # 키 기준 정렬

# print(player[0]) # (170, 72) # (키, 몸무게)
# print(player[0][0]) # 170 # 키
# print(player[0][1]) # 72 # 몸무게

cnt=0
flag=0
for i in range(n):
    for j in range(1,n-i):
        if player[i][1]<=player[i+j][1]: # 몸무게 비교
            flag=1 # 선수 제외
    if flag==0: # 선발
        cnt+=1 
    else:
        flag=0

print(cnt)

2중 for문은 시간복잡도 상으로 비효율적, for문 하나로 끝낼 수 있음

풀이

import sys
sys.stdin = open("./input/in6.txt", "rt")

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

# 키순으로 내림차순 정렬
player.sort(reverse=True)

largest=0
cnt=0

# 몸무게의 largest가 새로 갱신될 때만 cnt+=1
for h,w in player:
    if w>largest:
        largest=w
        cnt+=1

print(cnt)

정리

• 그리디는 대부분 “정렬”과 동반됨!
• 리스트에 튜플을 넣기: lst=[], lst.append((a,b))
• 튜플의 첫번째 요소(x[0]) 기준 (내림차순) 정렬: lst.sort(reverse=True)
• 🧐 2중 for문을 사용하지 않고, for문 한번으로 해결할 수 있는 논리: 키 기준 내림차순 정렬 후 몸무게의 max값 갱신마다 cnt+=1

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기