[백준 2220] 힙 정렬 (자바)

백준 2220번 힙 정렬 (자바)

 

 

출처

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

2220번: 힙 정렬

https://baelanche.tistory.com/132

[백준 2220] 힙 정렬

 

문제

힙은 자료의 추가, 우선순위가 제일 높은 자료의 삭제가 가능한 자료구조이다. 이와 같은 힙에는 두 종류가 있는데, 각각 최소-힙, 최대-힙이다. 이 문제에서는 최대-힙을 다루기로 하자.

이와 같은 최대-힙을 이용하면 O(n log n)정렬인 힙 정렬을 할 수 있다. 우리가 다루기로 한 최대-힙을 이용하면 오름차순 정렬을 할 수 있다. 힙 정렬은 크게 두 개의 단계로 나뉘는데, 첫 번째 단계는 주어진 자료들로 힙을 구성하는 단계이고, 두 번째 단계는 이렇게 구성된 힙에서 최댓값을 계속 제거하는 단계이다.

예를 들어 (5, 4, 2, 1, 3)과 같은 힙을 살펴보자. 이 힙에서 최댓값을 삭제하면 (3, 4, 2, 1)이 되고, 힙의 조건을 맞추기 위해 Swap을 한 번 하면 (4, 3, 2, 1)의 힙을 얻는다. 이 힙에서 최댓값을 삭제하면 (1, 3, 2)이 되고, 힙의 조건을 맞추기 위해 Swap을 한 번 하면 (3, 1, 2)가 된다. 다음 단계에서는 (2, 1), (1)이 되고 힙 정렬이 종료된다. 즉, 힙이 (5, 4, 2, 1, 3)과 같이 구성되어 있었다면, 정렬을 위해 Swap을 두 번 사용하게 된다. 하지만 (5, 4, 3, 2, 1)과 같은 힙은 총 네 번의 Swap을 해야 한다.

n이 주어졌을 때, 1부터 n까지의 수를 한 번씩 사용하여 만들 수 있는 힙들 중에서, 위와 같은 Swap 회수가 최대가 되도록 하는 힙을 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 n이 주어진다. (n<=100,000)

 

 

출력

첫째 줄에 n개의 정수로 힙을 출력한다.

 

 

입출력 예

 

입출력 예

 

 

한 줄 요약

트리에서 노드 i의 부모 노드 인덱스는 i/2라는 것을 활용해 루트 노드에는 계속 최댓값을 넣어주고 나머지 원소를 하나씩 뒤로 미룬다.

 

 

 

내 코드

1. 숫자를 입력받고 숫자+1 크기의 배열을 하나 선언한다.

2. 1~n까지의 수가 주어지므로 1~n-1까지 반복문을 돌린다

3. 노드 i의 부모 인덱스는 i/2 인 것을 활용하여 j=i ~ 1 이상까지 /=2를 하며 반복문을 돌린다. 그리고 j번째에 j/2번째 원소를 넣는다. (최솟값과 최댓값을 변경하고, 자식 노드가 부모 노드보다 크면 교환한다.)

4. 1번째에 i+1을 넣는다. (최댓값을 루트 노드에 넣는다.)

5. 필자는 값이 어떻게 출력되는지 보고 싶어 출력문을 추가했다.

6. 마지막으로 n번째에 1을 넣는다. (최솟값을 마지막 노드에 넣는다.)

import java.util.Scanner;

public class Heap_Sort {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] array = new int[n+1];
		
		
		for (int i=1; i<n; i++) {
			for (int j=i; j>1; j/=2) {
				array[j] = array[j/2];
			}
			
			array[1] = i+1;
			
			for (int j=1; j<array.length; j++) {
				System.out.println("array[" + j + "]" + array[j]);
			}
			System.out.println();
		}
		
		array[n] = 1;
		for (int i=1; i<=n; i++) {
			System.out.print(array[i] + " ");
		}
		
	}
}

 

 

고려할 점

1. j /=2를 활용해 for문을 돌리고 j번째에 값을 넣는 것

2. 루트 노드에는 최댓값이 들어가야 하므로 array[1] = i+1을 넣는 것

3. n번 노드에는 최솟값이 들어가야 하므로 1을 넣는 것