[백준] 7568번: 덩치 (빠른 풀이, C++)

https://www.acmicpc.net/problem/7568

평균 시간 복잡도 O(N^2)으로 푸는 문제인데, O(NlogN)의 풀이 방법이 생각나서 직접 풀어보았다.

미리 말하자면, 입력 숫자의 제한이 작기 때문에 O(N^2)로 풀어도 충분한 문제이다.

채점 결과에서도 더 빠른 풀이가 눈에 띄는 속도 차이를 보이진 않는다.

문제 설명

질문 게시판을 봐도 같은 내용의 질문이 많은데,

문제의 순위 세는 방식은 문제 속 자신보다 더 "큰 덩치"의 사람의 수를 센다.

이 방식은 2등이 3명이라고 꼭 3, 4등이 없으리란 보장이 없다.

[예시 (키, 몸무게)]

• A: (80, 180): 1등
• B: (70, 170): 2등
• C: (60, 170): 2등
• D: (50, 170): 2등
• E: (65, 165): 3등

방법 1: Brute-force (시간 복잡도 O(N^2))

제한에 N이 50 이하, 키와 몸무게가 200 이하이기 때문에, O(N^2)의 평균 시간 복잡도로 풀면 된다.

Profile 구조체를 이용하였고, 총 N명의 사람을 다른 N - 1명의 사람과 비교해 자신보다 더 큰 덩치를 가진 사람의 수를 센다.

#include <iostream>
#include <vector>

struct Profile {
  short height;
  short weight;
  short rank;

  bool operator>(const Profile &r) const {
    return ((height > r.height) && (weight > r.weight));
  }
};

int main() {
  short N;
  Profile profile;
  std::vector<Profile> v;

  std::cin >> N;
  for (short i = 0; i < N; i++) {
    std::cin >> profile.weight >> profile.height;
    v.push_back(profile);
  }

  for (short i = 0; i < N; i++) {
    v[i].rank = 1;
    for (short j = 0; j < N; j++) {
      v[i].rank += (v[j] > v[i]);
    }
  }

  for (auto item: v) {
    std::cout << item.rank << ' ';
  }
  std::cout << '\n';

  return 0;
}

방법 2: O(NlogN)

키 축과 몸무게 축의 2차원 좌표 평면이라고 생각했다.

가장 오른쪽 점부터 왼쪽 점으로 가면서, 해당 점보다 오른쪽 위(키와 몸무게가 큰)에 있는 점의 개수를 세면 된다.

이때, 지나간 점들은 다음 점보다 몸무게가 큰 점들이었기 때문에, 다음 점의 순위를 셀 땐 키만 비교하면 된다!

의사 코드는 다음과 같다. 몸무게 순서대로 비교한다고 했지만, 같은 몸무게가 나오는 상황을 처리해야 하는 점이 까다로웠다.

- buffer: w가 같은 점들의 높이를 임시로 저장하는 배열
- great_heights: 현재 점보다 w가 큰 점들의 키만 저장되는 트리

1. 점들을 w 축으로 정렬한다.
2. for 모든 점들에 대해 반복 (w가 큰 점부터)
    2-1. 점의 w가 줄어들었다면, buffer에 있는 점들을 great_heights에 추가한다.
    2-2. buffer에 현재 점의 height를 추가한다.
    2-3. great_heights에서 현재 점의 키보다 높은 점의 개수를 구한다.

해당 방식의 주요 시간 복잡도는 다음과 고려한다.

단계 1에서 점을 정렬하기 위해 O(NlogN)을 사용한다.

단계 2-3에서 great_heights 트리에 키를 추가하기 위해 O(logN)을 사용한다. 반복문 안에 있기 때문에 최종적으로는 O(NlogN)이 된다.

평균 시간 복잡도는 O(NlogN)이다.

실제 C++ 작성한 코드는 다음과 같다.

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

struct Profile {
  short index;
  short weight;
  short height;

  bool operator<(const Profile &r) const {
    return weight < r.weight;
  }
};

int main() {
  short N, prev_weight = 0;
  short *ranks;
  Profile profile;
  std::vector<Profile> v;
  std::vector<short> height_buffer;
  std::multiset<short> great_heights;

  // Input
  std::cin >> N;
  ranks = new short[N];
  for (short i = 0; i < N; i++) {
    profile.index = i;
    std::cin >> profile.weight >> profile.height;
    v.push_back(profile);
  }

  // Sort profiles by weight
  std::sort(v.begin(), v.end());

  // Scan data in order of great weight
  for (short i = N - 1; i >= 0; i--) {
    // Add height in great_heights if weight is different
    if ((v[i].weight != prev_weight)) {
      for (auto item: height_buffer) {
        great_heights.insert(item);
      }
      height_buffer.clear();
    }

    ranks[v[i].index] = std::distance(great_heights.upper_bound(v[i].height), great_heights.end()) + 1;
    height_buffer.push_back(v[i].height);
    prev_weight = v[i].weight;
  }

  for (short i = 0; i < N; i++) {
    std::cout << ranks[i] << ' ';
  }
  std::cout << '\n';

  return 0;
}

결론

제한이 작아서 시간은 정확히 측정되지 않는다. 여유가 있다면 직접 비교해보는 걸로..

결론적으로는 코드는 2배 더 길고, 메모리는 약간 더 많이 차지하는 코드가 되어버렸다ㅎ

누군가 같은 문제로 입력 제한이 높은 문제를 출제해주면 좋겠다.

찾아보니 나는 백준 문제 제출할 자격이 안 되더라..