[백준]힙 정렬

백준저지

[힙 정렬]https://www.acmicpc.net/problem/2220

• 힙 자료구조 삭제에 대한 이해도를 가지고

• 백준에서 제시된 예시 (5, 4, 3, 2, 1)과 (6, 5, 3, 2, 4, 1)에 대해 삭제를 펜으로 몇 번 해보았는데

• 규칙이 금방 발견되었다.

• 동적 알고리즘의 냄새가 물씬 나서 혹시나 하는 생각에 (2 ~ 1)과 (3 ~ 1)부터 (6 ~ 1)까지 힙을 그려 봤는데 동적 알고리즘이었다.

 

[구현]

• 먼저 첫 번째 규칙은 최댓값을 삭제 했을 때, 무조건 전 값의 힙 모양이 나온다는 것이었다.

• 예를 들어 (6, 5, 3, 2, 4, 1)에서 6을 삭제하게 되면 무조건 5일 때 최대로 swap이 되는 모양의 힙이 나온다는 것이다. 즉, (5, 4, 3, 2, 1)이 된다.

• 마찬가지로 (5, 4, 3, 2, 1)에서 5를 삭제하게 되면 4일 때 최대로 swap되는 모양의 힙인 (4, 2, 3, 1)이 나온다는 것이다.

• 두 번째 규칙은 최대의 swap을 위해 무조건 1이 힙에서 가장 끝에 위치해야 된다는 점이다.

• 즉 다시 말해서 최댓값이 삭제가 되면 (힙 삭제 규칙 상) 1이 최댓값 자리로 swap(이 스왑은 힙 삭제 규칙이기 때문에 교환 횟수로 간주하지 않는다.)이 되게 되고, 이 때부터 1은 힙 정렬의 끝의 자리를 목표점으로 교환이 되어야 한다는 점이다.

• 예를 들어 3의 경우 (4, 3, 2, 1)와 (4, 2, 3, 1)의 총 2가지 경우가 존재하게 되는데,

• (4, 3, 2, 1)의 경우 (1, 3, 2) → (3, 1, 2) swapCnt++

• (3, 1, 2)의 경우 (2, 1)

• 총 1번의 교환이 이루어지게 되는데, 이는 swap된 1의 위치가 힙의 끝에 위치하지 않기 때문이다.

• 그렇다면 (4, 2, 3, 1)의 경우를 보자.

• (4, 2, 3, 1)의 경우 (1, 2, 3) → (3, 2, 1) swapCnt++

• (3, 2, 1)의 경우 (1, 2) → (2, 1) swapCnt++

• 총 2번의 교환이 이루어지게 된다. 여기서 중요한 것은 (4, 2, 3, 1)의 삭제 결과 (3, 2, 1)은 최대로 swap이 많이 되는 힙 모양이다.

 

• 그렇다면 구현을 어떻게 해야 될까?

• 필자는 동적 알고리즘답게 2부터 시작해서 입력 값까지의 힙 모양을 구하는 방식으로 구현을 진행하였다.

• i=1일 때, vecArr[1]=1로 세팅을 하고,

• i=2일 때, 힙의 맨 마지막에 2를 삽입(vecArr[2]=2)하고 숫자 1을 힙의 맨 마지막에 두어야 하니까 vecArr[1]과 vecArr[2]를 swap한다.

• 그리고 최대 힙 모양을 맞춰야 하니까 while문(20번째 라인)을 통해 최대 힙 모양을 만든다.

• 사실 이게 전부다. 필자도 풀면서 혹시나 하는 마음에 몇 개를 더 해봤는데 한 번 해보시길 바란다.

• 결과는 변함이 없을 것이다.

• i=3일 때, 힙의 맨 마지막에 3을 삽입(vecArr[3]=3)하고 숫자 1을 힙의 맨 마지막에 두어야 하니까 (2, 1, 3)모양에서 vecArr[2]와 vecArr[3]을 교환한다. 그러면 (2, 3, 1) 모양이 되고 최대 힙을 위해 vecArr[1]과 vecArr[2]를 교환한다. 그러면 (3, 2, 1)일 때 swap이 가장 많이 되는 힙이 된다.

• 자 마지막으로 i=4일 때를 진행해보자

• i=4일 때, 힙의 맨 마지막에 4를 삽입(vecArr[4]=4)하고 숫자 1을 힙의 맨 마지막에 두어야 하니까 (3, 2, 1, 4)모양에서 vecArr[3]과 vecArr[4]를 교환한다. 이쯤 되면 1의 위치는 항상 맨 마지막에 존재한다는 것을 눈치 챘을 것이다. 그러면 (3, 2, 4, 1)이 되고 최대 힙을 맞추기 위해 vecArr[3]과 vecArr[1]을 교환한다. 이것도 INDEX로 따지면 2를 나눈 값과 교환하는 것을 눈치 챌 수 있다. 그러면 (4, 2, 3, 1)이 되고 4일 때 교환이 가장 많이 되는 힙 배열은 (4, 2, 3, 1)이 된다.

• 이 후 과정은 생략하도록 하겠다.

• 아래는 필자가 짠 코드이다.

• 혹시 더 빠르거나 더 좋은 알고리즘이 있다면 코멘트 바란다.

#include <iostream>
#include <vector>

using namespace std;

void SwapArr(vector<int>& vecArr, int n1, int n2) {
	int tmp = vecArr[n1];
	vecArr[n1] = vecArr[n2];
	vecArr[n2] = tmp;
}

int main(void) {
	int num;
	cin >> num;
	vector<int> vecArr(num+1, 0);
	vecArr[1] = 1;
	for (int i = 2; i <= num; i++) {
		vecArr[i] = i; int j = i-1;
		SwapArr(vecArr, i, i - 1);
		while (j != 1) {
			SwapArr(vecArr, j, j / 2);
			j = j / 2;
		}
	}

	for (int i = 1; i <= num; i++)
		cout << vecArr[i] << " ";

	return 0;
}