백준 2220 힙정렬

 

2220번: 힙 정렬

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

 

#include <stdio.h>
int main()
{
	int arr[100000] = {0};
	int N, idx, tmp, size, numOfData;
	arr[1] = 1;
	numOfData = 1;
	scanf(" %d", &N);
	idx = 1;
	for(int i= 2; i<=N-1; i++)//1~N-1까지 삽입
	{
		idx = numOfData + 1;
		while (idx != 1 && idx /2 != 1)
		{
			if (i > arr[idx / 2])
			{
				arr[idx] = arr[idx / 2];
				idx = idx / 2;
			}
			else
				break;
		}
		arr[idx] = i;
		numOfData += 1;
	}
	arr[1] = N;
	arr[N] = 1;
	for (int i = 1; i <= N; i++)
		printf("%d ", arr[i]);
	return 0;
	
}

 

swap의 횟수를 최대로 하기 위해서는 마지막 원소가 1이면 된다.  N을 입력했을 때 arr[N] = 1이면 된다는 것이다. 

그렇다면 이를 역순으로 생각해보자. 위의 그림을 통해 1을 배열의 첫번째 원소로 정해놓고 마지막에 1과 6을 바꿔주면 된다.