[파이썬/Python] 백준 7568번: 덩치

📌 문제 : 백준 7568번

---

📌 문제 탐색하기

N : 전체 사람 수 (2 ≤ N ≤ 50)
x : 몸무게 (10 ≤ x ≤ 200)
y : 키 ( 10 ≤ y ≤ 200)

✅ 입력 조건
1. N 입력
2. N개의 x, y가 공백으로 구분되어 입력
✅ 출력 조건
1. N명의 사람들의 덩치 등수를 구해 순서대로 첫 줄에 공백으로 분리하여 출력

덩치가 큰 사람 : 몸무게, 키를 비교해서 둘다 더 큰 사람을 의미.

덩치를 비교할 수 없는 경우 : 몸무게 더 나감 & 키가 더 작음

각 사람의 덩치 등수는 자신보다 더 큰 덩치의 사람 수를 의미한다.
→ 자신보다 더 큰 덩치의 사람 수가 k이면 덩치 등수 = k+1

이중 for문으로 N명의 사람을 돌아가면서 다른 사람의 덩치와 비교해서 키와 몸무게가 모두 더 큰 사람의 수를 count한다.

가능한 시간복잡도

N개 입력받기 → $O(N)$
이중 for문 → $O(N^2)$

최종 시간복잡도
$O(N^2)$로 2 ≤ N ≤ 50 조건에서
최악의 경우, $O(50^2)$이므로 1억번 내에 연산이 가능하다.

알고리즘 선택

이중 for문으로 비교해가며 갯수 세기

---

📌 코드 설계하기

0. 필요한 변수 정의
1. N 입력
2. N 반복해서 (x, y) 입력
3. for문으로 N개의 (x, y) 반복
4. for문으로 첫번째 for문의 (x, y)와 나머지를 비교
5. 몸무게, 키가 모두 더 큰 경우를 count
6. count+1한 수를 리스트에 append
7. 원하는 결과 출력
   
   

---

📌 시도 회차 수정 사항

---

📌 정답 코드

import sys

input = sys.stdin.readline

# 0. 필요한 변수 정의
rank = []

# 1. `N` 입력
N = int(input())

# 2. N 반복해서 (x, y) 입력
sizes = [list(map(int, input().split())) for _ in range(N)]

# 3. for문으로 N개의 (x, y) 반복
for size in sizes:
    count = 0

    # 4. for문으로 첫번째 for문의 (x, y)와 나머지를 비교
    for rest in sizes:
        # 5. 몸무게, 키가 모두 더 큰 경우를 count
        if size[0] < rest[0] and size[1] < rest[1]:
            count += 1

        else:
            continue

    # 6. count+1한 수를 리스트에 append
    rank.append(count+1)

# 7. 원하는 결과 출력
print(*rank)

• 결과
  

---

📌 회고

• 이중 for문을 사용했지만 입력 크기가 작아서 잘 작동했던 것 같다.
• 이런 식으로 모든 경우의 수를 하나하나 확인하면서 푸는 방법을 완전 탐색, Brute-Force(브루트 포스)라고 한다.