728x90
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)
사실은 간단했던 것이었다..
반응형
'🚩 Coding Test > Baekjoon' 카테고리의 다른 글
[BOJ][Python] 17626 Four Squares (0) | 2025.02.09 |
---|---|
[BOJ][Python] 18110 solved.ac / round() 반올림 안 되는 문제 (0) | 2025.02.07 |
[BOJ][Python] 26265 멘토와 멘티 (0) | 2025.02.05 |
[BOJ][Python] 2108 통계학 (1) | 2025.02.01 |
[BOJ][Python] 1018 체스판 다시 칠하기 (0) | 2025.02.01 |