그리디 문제 #2. 씨름선수

*이 풀이는 인프런: 파이썬 알고리즘 문제풀이 강좌에 기반하였습니다.

 

 

 

 

내 풀이

 

1. 지원자들의 키와 몸무게를 튜플로 저장하고, 키 순서에 따라 정렬한다.

키 순서대로 정렬하면, 해당 지원자의 다음 지원자들은 모두 키가 큰 것이기 때문에 해당지원자가 뽑히기 위해서는 다음 지원자들의 몸무게보다 커야한다.

따라서 몸무게만 비교를 해주면 된다. 

 

2. 해당 지원자의 몸무게보다 큰 다음 지원자가 있다면 뽑힐 수 없기 때문에 break를 통해 중단하고, break에 걸리지 않고 반복문이 끝까지 수행되었다면 해당지원자의 몸무게보다 큰 지원자가 없기 때문에 cnt의 값을 1 증가시켜준다.

 

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

n=int(input())
people=[]
for _ in range(n):
    h,w=map(int,input().split())
    people.append((h,w))
people.sort()
cnt=0
for i in range(n):
    w=people[i][1]
    for j in range(i+1, n):
        if people[j][1]>w:
            break
    else:
        cnt+=1
print(cnt)

 

 

 

 

강사님 풀이

 

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

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)

 

 

 

 

배운 점

 

1. 그리디 알고리즘은 정렬 후에 순차탐색하면서 가장 좋은 것을 선택하는 풀이 방법이다. 탐색해나가면서 가장 좋은 값을 갱신시켜야 한다.

 

2. 더이상 고려하지 않아도 되는 요소가 있다면, 그 요소를 제외하고 나머지 요소의 규칙만 분석하자.