백준 7568번 덩치 문제 풀이 Python

🔷 백준 7568번 — 덩치

---

비교 조건 기반 등수 계산 / 구조적 개선 vs 성능 문제는 여전히 O(N²)

---

📌 문제 설명

사람의 덩치를 (몸무게, 키) 두 가지 값으로 나타내고, 이를 비교해 등수를 매기는 문제입니다.
두 사람 A와 B에 대해

• A의 몸무게 > B의 몸무게
• A의 키 > B의 키

둘 다 만족해야 A의 덩치가 B보다 크다고 판단합니다.

등수는 아래 규칙으로 계산합니다:

한 사람보다 덩치가 더 큰 사람 수를 k라고 하면, 그 사람의 등수는 k + 1

---

🧠 예제

예를 들어 다음과 같이 5명이 있다고 할 때:

55 185  
58 183  
88 186  
60 175  
46 155

• (88, 186) → 누구보다도 크기 때문에 1등
• (46, 155) → 모두보다 작으므로 5등
• 나머지는 모두 C보다만 작으므로 2등

출력은:

2 2 1 2 5

---

💡 풀이 아이디어

• 모든 사람을 사용자 정의 자료형(Person 클래스)으로 표현
• 이중 반복문을 사용해 모든 사람 쌍을 비교
• 몸무게와 키가 모두 클 경우에만 등수 판정
• 기본 등수는 1로 시작하여, 더 큰 사람이 있으면 +1

---

✅ 전체 코드 (기초 구조, O(N²))

class Person:
    def __init__(self, weight, height):
        self.weight = weight
        self.height = height
        self.k = 1  # 등수는 1부터 시작

N = int(input())
persons = []

for _ in range(N):
    w, h = map(int, input().split())
    persons.append(Person(w, h))

for i in range(N):
    for j in range(N):
        if i != j:
            if persons[j].weight > persons[i].weight and persons[j].height > persons[i].height:
                persons[i].k += 1

for person in persons:
    print(person.k, end=' ')

---

🔎 세부 설명

✅ 클래스 구조

class Person:
    def __init__(self, weight, height):
        self.weight = weight
        self.height = height
        self.k = 1

• weight, height: 덩치의 기준
• k: 등수, 기본값 1로 초기화

---

✅ 비교 방식 (이중 반복문)

for i in range(N):
    for j in range(N):
        if i != j and persons[j].weight > persons[i].weight and persons[j].height > persons[i].height:
            persons[i].k += 1

• 모든 사람끼리 쌍으로 비교 (O(N²))
• i보다 덩치가 큰 j가 존재하면, i의 등수를 올림

---

❗ 성능에 대한 명확한 정리

이 코드는 O(N²) 시간 복잡도입니다.
하지만 문제에서 2 ≤ N ≤ 50이므로 성능에 전혀 문제가 없습니다.

만약 N이 수천, 수만 명이라면 이 방식은 성능 이슈가 발생합니다.

✅ 이 글의 핵심 포인트

• "덩치 등수 계산"은 본질적으로 모든 사람과 비교해야 하므로
• O(N²) 이상의 개선은 문제 정의상 어렵습니다.
• 즉, 성능을 개선하려면 문제 조건 자체가 달라져야 합니다.

---

🔧 구조적 개선 (가독성과 유지보수 개선)

성능은 그대로지만, 코드를 객체지향적으로 정리하면 의미가 명확해집니다.

class Person:
    def __init__(self, weight, height):
        self.weight = weight
        self.height = height
        self.k = 1

    def is_bigger_than(self, other):
        return self.weight > other.weight and self.height > other.height

이렇게 분리하면 비교 코드가 훨씬 명확하고 읽기 쉬워집니다:

for i in range(N):
    for j in range(N):
        if i != j and persons[j].is_bigger_than(persons[i]):
            persons[i].k += 1

---

✅ 정리 요약

구분	설명
비교 기준	몸무게, 키 둘 다 커야 "덩치가 더 크다"
등수 판단	더 큰 사람 수 + 1
시간 복잡도	O(N²) (성능 개선은 없음)
구조적 개선	클래스 메서드 분리로 가독성 향상

---

💬 마무리 코멘트

이 문제에서 중요한 건 성능 최적화가 아니라, 조건을 정확하게 구현하는 것입니다.
성능이 중요한 문제였다면 O(N log N) 알고리즘을 고민했어야 했지만,
이 문제는 N이 작고, 조건 구현이 더 중요하므로 클래스를 활용한 깔끔한 구현이 포인트입니다.

---

✨ 다음 확장 아이디어

• __lt__ 연산자 오버로딩해서 정렬 가능하게 만들기
• JSON 파일로 사람 정보 저장 및 불러오기
• GUI로 시각화된 덩치 등수 만들기 (tkinter 등)