[BOJ][Python] 7568 덩치

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: 실버 5
• 문제 유형: 구현, 브루트포스
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

이미지 클릭 시 문제로 이동

 

[코드]

처음에는 몸무게, 키 내림차순으로 정렬하고, 앞의 (몸무게, 키) 쌍과 비교해주었다. 

(실패 코드)

import sys
input = sys.stdin.readline
N = int(input())
lst = [tuple(map(int, input().strip().split())) for _ in range(N)]
# print(lst)

sorted_lst = sorted(lst, key=lambda x: (x[0], x[1]), reverse=True)
# print(sorted_lst)

tmp, cnt = {}, 0
mx_w, mx_h, rank = sorted_lst[0][0], sorted_lst[0][1], 1
for kg, cm in sorted_lst:
    # print(mx_w, mx_h, cnt)

    # 몸무게, 키 둘 다 작을 때 순위 + (앞의 사람 수)
    if mx_w > kg and mx_h > cm:
        rank += cnt
        tmp[(kg, cm)] = rank
        cnt = 1

    else:
        cnt += 1
        tmp[(kg, cm)] = rank
        
    mx_w, mx_h = kg, cm    

result = []
for l in lst:
    result.append(tmp[l])

print(*result)

반례를 찾지 못해 답답했는데, 몸무게를 먼저 내림차순으로 정렬해주고 키를 내림차순으로 정렬하기 때문에

(70, 180), (68, 175), (65, 186)

 

내가 처음 짠 코드대로 실행하면, 1 2 2 가 된다. 

그러나 몸무게 또는 키 중 하나라도 크다면 순위가 동등하므로 1 2 1 이 된다.

모든 사람과 비교하여 각자 자기 덩치보다 큰 사람의 수를 세면 되는 것이다. 

각 사람별로 다른 사람과 비교:

(70,180):

• (68,175)보다 키,몸무게 모두 큼
• (60,185)보다 몸무게만 큼, 키는 작음

(68,175):

• (70,180)보다 둘 다 작음
• (60,185)보다 몸무게만 큼, 키는 작음

(60,185):

• (70,180)보다 키만 큼, 몸무게는 작음
• (68,175)보다 키만 큼, 몸무게는 작음

따라서 순위: 1 2 1

• 70,180: 자신보다 덩치 큰 사람 0명 -> 1등
• 68,175: 자신보다 덩치 큰 사람 1명 -> 2등
• 60,185: 자신보다 덩치 큰 사람 0명 -> 1등

 

(정답 코드)

N = int(input())
lst = [tuple(map(int, input().split())) for _ in range(N)]
ranks = []

for i in range(N):
    rank = 1
    for j in range(N):
        if lst[j][0] > lst[i][0] and lst[j][1] > lst[i][1]:
            rank += 1
    ranks.append(rank)
    
print(*ranks)

 

사실은 간단했던 것이었다..