백준 7568번 덩치 문제 C++

🔷 백준 7568번 — 덩치 (C++ 버전)

---

비교 조건 기반 등수 계산 / 구조적 설계 vs 성능은 O(N²) 그대로

---

📌 문제 설명

사람의 덩치를 (몸무게, 키) 두 가지 수치로 나타내고, 이를 이용해 덩치 등수를 계산하는 문제입니다.
두 사람이 있을 때,

• 몸무게도 크고
• 키도 크다면

그 사람을 더 "덩치가 크다"고 합니다.

한 사람보다 덩치가 큰 사람이 k명이면,
그 사람의 등수는 k + 1

---

💡 풀이 아이디어

• struct를 이용해 사람 정보를 묶은 사용자 정의 자료형 Person을 생성
• Person 배열을 동적 할당해서 모든 사람의 정보를 저장
• 이중 반복문을 통해 모든 쌍을 비교하여 덩치 비교 수행
• 더 큰 사람이 있으면 k++ → 등수는 기본적으로 1로 시작

---

✅ 전체 코드

#include <iostream>
using namespace std;

struct Person {
    int weight;
    int height;
    int k = 1;  // 등수는 기본값 1로 설정
};

int main() {
    int n;
    cin >> n;

    // 동적 배열 할당
    Person* p = new Person[n];

    // 입력 받기
    for (int i = 0; i < n; i++) {
        cin >> p[i].weight >> p[i].height;
    }

    // 덩치 비교
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i].weight > p[j].weight && p[i].height > p[j].height) {
                p[j].k++;
            } else if (p[i].weight < p[j].weight && p[i].height < p[j].height) {
                p[i].k++;
            }
        }
    }

    // 출력
    for (int i = 0; i < n; i++) {
        cout << p[i].k << " ";
    }
    cout << endl;

    // 메모리 해제
    delete[] p;
    return 0;
}

---

🔍 세부 설명

✅ 구조체 정의

struct Person {
    int weight;
    int height;
    int k = 1;
};

• 몸무게, 키, 등수 k를 하나로 묶은 자료형
• 등수 k는 기본값 1로 시작

---

✅ 덩치 비교 로직

for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        if (p[i].weight > p[j].weight && p[i].height > p[j].height) {
            p[j].k++;
        } else if (p[i].weight < p[j].weight && p[i].height < p[j].height) {
            p[i].k++;
        }
    }
}

• 모든 사람끼리 쌍을 비교
• 키와 몸무게 모두 큰 경우에만 상대방 등수를 증가

---

❗ 성능은 그대로 O(N²)

• 이중 반복문이기 때문에 시간 복잡도는 O(N²)
• 문제 조건(N ≤ 50)이 작기 때문에 성능 문제는 없음

💬 이 풀이의 핵심은 정확한 조건 구현이지, 성능 최적화가 아닙니다.

---

🧠 구조적으로 깔끔한 이유

• struct Person을 사용하여 관련 데이터를 묶었고
• 동적 배열을 사용하여 입력 개수에 따라 유연하게 대응
• 반복문을 통해 모든 쌍을 비교하되, 덩치가 더 큰 경우에만 등수 증가
• 명확하고 직관적인 비교 조건

---

✅ 요약 정리

구분	설명
구조체 사용	struct Person으로 몸무게, 키, 등수 묶기
배열 구조	동적 배열(new)로 유연하게 저장
등수 계산	(몸무게, 키) 모두 클 때만 상대방 등수 증가
시간 복잡도	O(N²) (성능 문제 없음)

---

📚 확장 아이디어

• class로 바꾸고 멤버 함수로 is_bigger_than() 추가 (OOP 설계 개선)
• std::vector 사용해서 메모리 자동 관리
• operator< 오버로딩해서 std::sort로 정렬된 덩치 보기
• GUI 시각화나 파일 입출력 추가

---

📝 마무리

이 문제는 조건에 따라 등수를 판정하는 시뮬레이션 문제입니다.
비교 조건을 잘 구현하고, 모든 쌍을 정확하게 비교하는 게 핵심입니다.
구조체를 이용한 코드 설계는 가독성과 유지보수성을 높이는 데 큰 도움이 됩니다.
성능이 문제가 되지 않으므로, 조건 구현에 집중하는 것이 올바른 방향입니다.