[백준 2220] 힙 정렬 (C#, C++) - soo:bak

문제 링크

2220번 - 힙 정렬

설명

1부터 N까지 수를 한 번씩 사용하여 최대 힙을 구성할 때, 힙 정렬 과정에서 자리 바꿈 횟수가 최대가 되는 초기 배열을 출력하는 문제입니다.

접근법

최대 힙에서 최댓값을 삭제하면 맨 끝 값이 루트로 올라오고, 힙 조건을 맞추기 위해 아래로 내려가며 자리를 바꿉니다. 예를 들어 5, 4, 3, 2, 1 힙에서 5를 삭제하면 1이 루트로 오고, 4와 바꾸고, 다시 2와 바꿔서 4, 2, 3, 1이 됩니다. 이처럼 루트로 온 값이 작을수록 더 깊이 내려가며 자리 바꿈이 많아집니다.

자리 바꿈을 최대화하려면 매번 삭제할 때 맨 끝에 있는 값이 가장 작아야 합니다. 그리고 그 값이 루트까지 올라온 뒤 가장 깊은 곳까지 내려가야 합니다.

이런 힙을 만드는 방법이 있습니다. 1을 루트에 넣고 시작합니다. 2를 추가할 때 맨 끝에 넣은 뒤 바로 앞 위치의 값과 바꿉니다. 그러면 1이 맨 끝으로 가고 2가 그 자리에 옵니다. 이제 2가 있는 위치에서 루트까지 부모와 계속 바꾸며 올라갑니다.

3, 4, 5, … 도 같은 방식으로 추가합니다. 새 수를 맨 끝에 넣고, 바로 앞 값과 바꾸고, 그 위치에서 루트까지 올라갑니다. 이렇게 하면 항상 1이 가장 깊은 곳에 있게 되고, N이 6이면 6, 5, 3, 2, 4, 1 같은 배열이 만들어집니다.

---

Code

C#

using System;
using System.Text;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var heap = new int[n + 1];
    heap[1] = 1;

    for (var i = 2; i <= n; i++) {
      heap[i] = i;
      (heap[i], heap[i - 1]) = (heap[i - 1], heap[i]);
      for (var j = i - 1; j > 1; j /= 2)
        (heap[j], heap[j / 2]) = (heap[j / 2], heap[j]);
    }

    var sb = new StringBuilder();
    for (var i = 1; i <= n; i++) {
      sb.Append(heap[i]);
      if (i < n) sb.Append(' ');
    }
    Console.WriteLine(sb);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi heap(n + 1);
  heap[1] = 1;

  for (int i = 2; i <= n; i++) {
    heap[i] = i;
    swap(heap[i], heap[i - 1]);
    for (int j = i - 1; j > 1; j /= 2)
      swap(heap[j], heap[j / 2]);
  }

  for (int i = 1; i <= n; i++)
    cout << heap[i] << (i == n ? '\n' : ' ');

  return 0;
}