[인프런] 씨름 선수

---

문제설명

현수는 씨름 감독이다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했다. "다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했다." 만약 A라는 지원자보다 키도 크고 몸구게도 무거운 지원자가 존재한다면 A지원자는 탈락이다.

입력조건

• 첫째 줄에 지원자의 수 N(5 <= N <= 50)이 주어진다.
• 둘째 줄부터 N명의 키와 몸무게 정보가 차례로 주어진다. 각 선수의 키와 몸무게는 모두 다르다.

출력조건

• 첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력한다.

사고과정

• 키 또는 몸무게 둘 중 하나 기준으로 오름차순 정렬한다. 예를 들어, 키를 기준으로 오름차순 정렬 했을 때, 밑에있는 사람들보다 몸무게가 작으면 무조건 탈락이다. 그래서 이중 loop로 구현했다.
• 그런데 풀이를 보니 하나의 Loop로도 해결이 가능했다. 바로 내림차순 정렬을 수행한 후, 키 또는 몸무게만 최댓값이 갱신되는지 확인하면 되는 것! 예를 들어, 키를 기준으로 내림차순 정렬한 다음 그 순서대로 몸무게의 최댓값이 갱신되면 탈락하는 사람이 없지만 중간에 몸무게 최댓값이 갱신되지 않으면 무조건 탈락이다.
• 이중 루프보다 일중 루프를 사용하는 것이 시간복잡도 면에서 효율적이므로 일중 루프를 사용하자! 그리디 방식에서 정렬을 사용하되 어떤 기준으로(오름/내림) 정렬하는지도 문제 해결에 많이 기여하는 듯 하다!

풀이

- 나의 풀이

n = int(input())
arr = []
for _ in range(n):
    h, w = map(int, input().split())
    arr.append((h, w))
arr.sort(key=lambda x: (x[0], x[1]))
weight = 0
fail = 0
for i in range(n):
    for j in range(i+1, n):
        if arr[i][1] < arr[j][1]:
            fail += 1
            #print('탈락대상:', arr[i], '탈락시킨 대상:', arr[j])
            break
print(n - fail)

- 강의 풀이

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)