글 읽기 - (힙정렬) 시간초과; N*LogN인데 왜 시간초과가 발생할까

ehdgml0106 3년 전 0

N*LogN인데 왜 시간초과가 발생하는지 모르겠습니다.

아무리 생각해도 시간초과가 발생할 이유를 찾지 못하겠습니다.

고수님들, 제 코드에 의심가는 부분이 있다면, 코멘트 부탁드립니다. 감사합니다.

#pragma warning(disable: 4996)
#pragma warning(disable: 6031)

#include <stdio.h>
#include <assert.h>

#define PARENT_IDX(idx)      ((idx-1) / 2)
#define LEFT_CHILD_IDX(idx)  (idx*2 + 1)
#define RIGHT_CHILD_IDX(idx) (idx*2 + 2)

const int MAX_NUM = ((int)1e5 + 10);
int N;

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void print(int* pArr, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", pArr[i]);
    }
    printf("\n");
}

int main()
{
    freopen("input.txt", "r", stdin);
    scanf("%d", &N);

    int array[MAX_NUM];
    int elementCnt = 0;
    for (int i = 0; i < N; i++)
    {
        int num;
        scanf("%d", &num);
        if (0 == num)
        {
            //root를 삭제하고, leaf를 root로 올린다.
            if (elementCnt <= 0)
            {
                printf("%d\n", 0);
                continue;
            }

            printf("%d\n", array[0]);
            array[0] = array[elementCnt - 1];
            elementCnt--;

            //Loop
            //exit condition: leaf에 도달 또는 자식노드들보다 크다.
            //do: 자식노드와 swap한다. 노드 위치를 업데이트한다.
            int idx = 0;
            int idxLeftChild = LEFT_CHILD_IDX(idx);
            int idxRightChild = RIGHT_CHILD_IDX(idx);
            int idxChild = idx;
            while (1)
            {
                if (idxLeftChild >= elementCnt) //leaf에 도달한 경우,
                {
                    break;
                }
                if (array[idx] < array[idxLeftChild])
                {
                    idxChild = idxLeftChild;
                }
                if (idxRightChild < elementCnt && array[idx] < array[idxRightChild])
                {
                    idxChild = idxRightChild;
                }
                if (idx == idxChild) //두 자식노드 이상인 경우,
                {
                    break;
                }
                swap(&array[idx], &array[idxChild]);
                idx = idxChild;
            }
        }
        else // (num != 0)
        {
            //삽입한다.
            array[elementCnt++] = num;

            //Loop
            //exit condition: root에 도달 또는 부모노드보다 작거나 같다.
            //do: 부모노드와 swap한다. 노드 위치를 업데이트한다.
            int idx = elementCnt - 1;
            int idxParent = PARENT_IDX(idx);
            while (idx > 0 && array[idx] > array[idxParent])
            {
                swap(&array[idx], &array[idxParent]);
                idx = idxParent;
                idxParent = PARENT_IDX(idx);
            }
        }
    }
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(힙정렬) 시간초과; N*LogN인데 왜 시간초과가 발생할까

ehdgml0106 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말