[백준] 2220 힙정렬 문제풀이 C++ :: 그리디 알고리즘 :: DANIDANI

2220 힙 정렬

www.acmicpc.net/problem/2220

2220번: 힙 정렬

 

문제를 보고, 먼저 예제의 답을 거꾸로 삭제해보았다.

삭제를 해보면서 보인 규칙은 크게 두 가지였다.

 

1. n번째 수를 삭제하면 n-1번째 수의 최대 swap 형태가 된다.

2. 항상 마지막은 1이다.

---

이를 바탕으로 생각한 문제 접근 방법은 다음과 같다.

1. 1부터 n까지 수를 차례로 힙에 넣는다.

2. 이때, k번째 수를 넣고 k와 1을 swap 한다.

3. 최대 힙을 구성한다.

4. 2-3 과정을 반복한다.

 

#include <iostream>

using namespace std;

int arr[100000];
void swap(int a, int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
int main(void){
    int n;
    cin >> n;

    arr[1]=1;
    for(int i = 2; i <= n;i++){
        arr[i] = i;
        
        // 1과 i 바꾸기
        swap(i-1, i);

        // 최대힙 구성
        for(int j = i - 1; j > 1; j /= 2){
            swap(j, j / 2);
        }
    }


    for(int i=1;i<=n;i++)
        cout<< arr[i]<<" ";
    return 0;
}

 

힙정렬에 대한 설명

2021/01/21 - [Algorithm/개념정리] - 힙정렬(Heap Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI