[C언어] 2751번 - 수 정렬하기 2 (힙 정렬, Heap Sort)

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

힙 정렬이란?

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

- 완전 이진 트리의 일종인 Heap 자료구조이다

- 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법이다

- 과정

 1. 정렬해야 할 n개의 요소들로 완전 이진 트리 형태를 만든다

 2. 한 번에 하나씩 요소를 힙에서 꺼내 배열에 저장한다

 3. 삭제된 요소를 다른 요소로 대체해 재정렬하며 반복한다

 

- 최대 힙의 삽입 과정

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

 

- 최대 힙의 삭제

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

 

1회 제출 코드 (시간초과)

#include <stdio.h>

void heapify(int *arr, int size);
void swap(int *arr, int x, int y);

int main(void) {

    int n, size;
    int arr[1000000] = {};

    scanf("%d", &n); //숫자 개수 입력

    for(int i = 0; i < n; i++) { //숫자 개수만큼 배열에 숫자 입력 받기
        scanf("%d", &arr[i]);
    }

    size = n; //maxheap 처리과정에서 size-- 되기 때문에 n에 영향 안주려고 따로 변수선언

    for(int i = 0; i < n; i++) {
        heapify(arr, size); //maxheap 구성
        swap(arr, 0, size - 1); //탑 노드와 제일 마지막 노드 교체 
        size--; //이미 찾은 최대값은 순서대로 배제
    }

    for(int i = 0; i < n; i++) { //숫자 개수만큼 순서대로 숫자 출력
        printf("%d\n", arr[i]);
    }

    return 0;
}

void heapify(int *arr, int size) {
    for(int i = 1; i < size; i++) { //첫번째 자식노드부터
        int child = i;

        while(child > 0) { //부모노드랑 교체가 일어났다면 탑노드까지 비교
            int root = (child - 1) / 2; //부모노드의 인덱스 계산

            if(arr[root] < arr[child]) { //자식노드가 더 큰 경우
                swap(arr, root, child); //서로 교체
                child = root; //부모노드를 자식노드로 하여 탑노드까지 비교
            }
            else { //아니면 건너뜀
                break;
            }
        }
    }
}

void swap(int *arr, int x, int y) {  //배열과 두 인덱스 값을 받아서 서로 바꿔줌
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

맨 처음 힙 정렬에 대한 원리를 이해하고서는

'아 그냥 입력 받은 배열을 힙 트리라고 생각하고 노드 하나하나 다 들려서 부모 노드가 자식 노드보다 큰 수를 가지게끔 정렬하고 끝나면 탑 노드랑 최하위 노드랑 교체하는거 반복하면 되겠네'

 

라고 생각해버렸다... 그래서 삽질이 시작되고 결국 테스트 케이스는 통과했는데 시간초과 발생

 

반복문이 너무 많은거 같아서 시간초과가 나는거라 생각하고 main함수에 for문을 없애고 heapify 함수에 do ~ while문을 추가했다

2회 제출 코드 (시간초과)

#include <stdio.h>

void heapify(int *arr, int size);
void swap(int *arr, int x, int y);

int main(void) {

    int n, size;
    int arr[1000000] = {};

    scanf("%d", &n); //숫자 개수 입력

    for(int i = 0; i < n; i++) { //숫자 개수만큼 배열에 숫자 입력 받기
        scanf("%d", &arr[i]);
    }

    size = n; //maxheap 처리과정에서 size-- 되기 때문에 n에 영향 안주려고 따로 변수선언

    heapify(arr, size);

    for(int i = 0; i < n; i++) { //숫자 개수만큼 순서대로 숫자 출력
        printf("%d\n", arr[i]);
    }

    return 0;
}

void heapify(int *arr, int size) {
    do {
        for(int i = 1; i < size; i++) { //첫번째 자식노드부터
            int child = i;

            while(child > 0) { //부모노드랑 교체가 일어났다면 탑노드까지 비교
                int root = (child - 1) / 2; //부모노드의 인덱스 계산

                if(arr[root] < arr[child]) { //자식노드가 더 큰 경우
                    swap(arr, root, child); //서로 교체
                    child = root; //부모노드를 자식노드로 하여 탑노드까지 비교
                }
                else { //아니면 건너뜀
                    break;
                }
            }
        }

        swap(arr, 0, --size);
    } while(size > 1);
}

void swap(int *arr, int x, int y) {  //배열과 두 인덱스 값을 받아서 서로 바꿔줌
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

do ~ while문으로 바꿨지만 역시나 for문이나 do ~ while문이나 둘 다 반복문... 또 시간초과였다

 

힙 정렬 원리상 반복문을 더 줄일 수는 없다.

시간 잡아먹는 부분을 찾아야겠다고 생각하고 구글링을 통해 최초 힙트리 생성과 힙 정렬을 나눠서 접근한 분을 찾았고

내 코드에서는 힙트리 생성이 매번 일어나고 모든 노드를 다 들리기 때문에 시간이 많이 소요되는 것을 발견

 

그래서 나도 최초 힙트리 생성과 힙 정렬을 따로 나누었다

최초 힙트리 생성을 수행하면서 부모-자식 노드 3개의 작은 트리에서는 부모 노드가 큰 수가 되게끔 정렬 돼있을테니까

힙 정렬을 수행할 때 노드를 일일히 들리는게 아니라 작은 트리의 부모 노드끼리만 비교해서 큰 수를 자리를 교체해가며 탑 노드까지 끌어올리면 되는거였다

3회 제출 코드 (통과)

#include <stdio.h>

void heapSort(int *arr, int n);
void swap(int *arr, int x, int y);

int main(void) {

    int n;
    int arr[1000000] = {};

    scanf("%d", &n); //숫자 개수 입력

    for(int i = 0; i < n; i++) { //숫자 개수만큼 배열에 숫자 입력 받기
        scanf("%d", &arr[i]);
    }

    heapSort(arr, n); //힙 정렬

    for(int i = 0; i < n; i++) { //숫자 개수만큼 순서대로 숫자 출력
        printf("%d\n", arr[i]);
    }

    return 0;
}

void heapSort(int *arr, int n) {
    int size = n;
    int root, child;

    //최초 힙트리 생성 후 탑 노드-최하위 노드 교체
    for(int i = 1; i < size; i++) {
        child = i;

        while(child > 0) {
            root = (child - 1) / 2;

            if(arr[root] < arr[child]) {
                swap(arr, root, child);
                child = root;
            }
            else {
                break;
            }
        }
    }

    swap(arr, 0, --size);

    //찾은 Max값은 배제해가며 남은 힙트리를 부모-자식 3개 노드 단위로 훑어 힙 정렬 수행
    while(size > 1) {
        root = 0;

        while(root <= ((size / 2) - 1)) {
            child = (root * 2) + 1;

            if(child + 1 < size && arr[child] < arr[child + 1]) {
                child++;
            }

            if(arr[root] < arr[child]) {
                swap(arr, root, child);
                root = child;
            }
            else {
                break;
            }
        }

        swap(arr, 0, --size);
    }
}

//배열과 두 인덱스 값을 받아서 서로 바꿔줌
void swap(int *arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

 

결국은 성공했다..