글 읽기 - 코드가 어디서 틀렸는지 알고 싶습니다

themion 3년 전 0

최대 힙의 정의에 맞게 코드를 작성했는데 자꾸 오답 처리가 발생하네요.

런타임 에러가 아니라 단순히 '틀렸습니다'인 걸로 봐선 인덱스 문제는 아니지 싶은데, 대체 어디서 문제가 발생하는 걸까요?

#include <cstdio>

#define MAX 100000

int heap[MAX] = { 0, }, len = 0;

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

int bigger_child(int idx)
{
    int l = 2 * idx + 1, r = 2 * idx + 2;
    return heap[l] > heap[r] ? l : r;
}

int pop()
{
    if (len == 0) return 0;

    int idx = 0, cmp = bigger_child(idx), ret = heap[idx];
    heap[idx] = heap[--len]; heap[len] = 0;

    while (cmp <= len && heap[idx] < heap[cmp])
    {
        swap(heap[idx], heap[cmp]);
        idx = cmp;
        cmp = bigger_child(idx);
    }

    return ret;
}

int push(int val)
{
    int idx = len++;
    heap[idx] = val;
    while (idx && heap[idx] > heap[idx / 2])
    {
        swap(heap[idx], heap[idx / 2]);
        idx /= 2;
    }

    return len;
}

int main()
{
    int N, num;
    scanf("%d", &N);
    while (N--)
    {
        scanf("%d", &num);
        num ? push(num) : printf("%d\n", pop());
    }

    return 0;
}

guts0rock 3년 전 3

저도 계속 "틀렸습니다"가 떠서 고생 좀 했는데요,

저는 Pop할 때 child가 둘 다 존재하는 경우,

하필 두 child가 같은 값을 가지고 있으면 정상적으로 swap을 하지 않는 게 문제였습니다.

즉, 두 child 중 누가 더 큰지만 판단하려고 했지, 같은 경우를 고려하지 못했었네요.

아무튼 그 부분을 수정했더니 해결되었어요~

아래 테스트케이스로 검증했습니다.

10
1 2 3 4 5 5 5 5 0 0

(출력이 5 5 로 나와야 하는데 5 1이 나오고 있었음)

themion 3년 전 0

bigger_child 함수의 부등호를 >에서 >=로 바꾸면 제대로 동작한다고 말씀하셨는데, 그 부분을 바꾸어도 결과에는 차이가 없었습니다.

또 말씀하신 테스트 케이스는 위에 작성된 코드로도 제대로 작동했습니다.

guts0rock 3년 전 0

네 저도 유사한 로직을 짰었는데 제가 해결한 방법을 한번 공유드려 봤습니다.

kth001 3년 전 0

제 코드처럼 하면 될겁니다

heap[idx] = heap[--len]; heap[len] = 0;// your code

heap[idx] = heap[len];//my code
heap[len] = 0;
len--;

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

문제

문제

출처

ICPC

코드가 어디서 틀렸는지 알고 싶습니다

themion 3년 전 0

guts0rock 3년 전 3

themion 3년 전 0

guts0rock 3년 전 0

kth001 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말