파이썬 알고리즘 027 | 씨름선수(그리디)

27. 씨름 선수(그리디)

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

<내 풀이>

p=[]
N=int(input())
for _ in range(N) : 
    s,e = list(map(int, input().split()))
    p.append([s,e])
p.sort(key=lambda x : (x[0],x[1])) #한번 써보고 싶었다..
k=0
for s,e in p :
    cnt=0
    for m,n in p:
        if s>m or e>n:
            cnt+=1
    if cnt==N-1:
        k+=1
print(k)

이렇게 풀면 시간복잡도가 커지게 된다, 이중 for문 사용은 비효율

<풀이>

• 키로 내림차순(큰 것부터 차례대로)하면
  183 65
  
  181 60
  
  180 70
  
  172 67
  
  179 72
  

이렇게 나오는데 밑에 있는 애들은 이미 키에서 다 졌으니깐
위에 있는 애들을 몸무게부분에서는 이겨야 한다
(키와 몸무게 중에서 하나는 이겨야하므로)
그래서 처음 키짱의 몸무게를 가장 크다고 설정해놓고 밑에서 더 큰게 있다면
밑의 몸무게로 대체한다.
위에 있는 애의 몸무게를 못 이기면 경우의 수에 포함시키지 않고 세지 않는다

p=[]
N=int(input())
for _ in range(N) : 
    s,e = list(map(int, input().split()))
    p.append([s,e])
p.sort(reverse=True) #키 내림차순으로, 큰 것부터 작은 것 순서로
largest=0
cnt=0
for x, y in p :
    if y>largest:
        largest=y
        cnt+=1
print(cnt)

<반성점>

• 최대한 이중 for문을 쓰기보다 저렇게 효과적인 접근법을 생각해내고 싶다

<배운 점>

• 두 개의 다른 항목을 비교하여 하나라도 큰 것을 찾을 때: 하나를 기준으로 내림차순으로 정렬하고 다른 하나는 서로 비교하여 가장 큰 값이 되면 하나라도 큰 것.