현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “다른 모든 지원자와 일대일 비교하여 키와 몸무게 중 적어도 하나는 크거나, 무거운 지원자만 뽑기로 했습니다.” 만약 A라는 지원자보다 키도 크고 몸무게도 무거운 지원자가 존재한다면 A지원자는 탈락입니다.
키와 몸무게 중 최소 하나라도 커야 한다는 말은 즉, 둘 다 동시에 작으면 안된다는 것이다.
<내 답안>
n = int(input())
li = [list(map(int, input().split())) for _ in range(n)]
li.sort()
cnt = 0 # 탈락 인원
for i in range(n):
for j in range(i+1, n):
if li[i][1] < li[j][1]:
cnt += 1
break
print(n-cnt)
그리디는 정렬과 함께 간다!!
나는 먼저 받은 데이터를 키 순으로 정렬했다.
키가 인덱스 0 이고 몸무게가 인덱스 1 이기 때문에 li.sort()만 해도 첫 순위인 키 순으로 오름차순 정렬이 된다.
여기서 몸무게 순으로 오름차순 정렬을 하려면, 첫 순위는 몸무게가 되어야 한다.
li.sort(key = lambda x : (x[1], x[0]))람다 함수를 이용하여 첫 순위를 몸무게, 그 다음 순위를 키로 바꾸면 된다.
여기서 내림차순으로 변경하고 싶다면, reverse = True 를 쓰면 된다.
- sort는 오름차순 정렬이고 reverse = False가 default 이다.
<모범답안>
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)나는 for문을 두 번 사용하였는데, 해설에서는 한 번 사용하여 푼다.
해설에서는 키 순으로 내림차순 정렬을 했기 때문에 몸무게만 비교하면 되어서 for문을 한 번만 사용하였다.
키와 몸무게를 튜플 형식으로 저장하여 for문의 조건에서 x, y로 바로 꺼낼 수 있다.
largest라는 최대값 변수를 선언하고 내림차순 되어있는 몸무게를 하나씩 비교하며 최대값보다 작으면 탈락, 크면 통과이다.
