글 읽기 - 최소 힙 문제를 플었는데 어느 부분이 틀렸는지 모르겠습니다.

master1511 4년 전 1

어디에 문제가 있는걸까요

아무거나 다 해봐도 잘 되는데 뭐가 문제인걸까요

#include <iostream>
#include<stdio.h>
using namespace std;
int arr[100005] = {0}, sz = 0;
//sz = 현재 힙 크기

//삽입 할 경우
void insert(int val) {
	sz++;
	arr[sz] = val;
	int i = sz, temp = 0;
    
    //만약 부모의 노드가 내 노드보다 크다면 
	while (arr[i / 2] > arr[i]) {
		temp = arr[i / 2];
		arr[i / 2] = arr[i];
		arr[i] = temp;
		i = i / 2;
        //교환해준 후 부모의 노드의 위치로 이동해서 같은 작업을 반복한다.
        //arr[0]은 항상 0이고, 자연수만 힙에 입력할 수 있으므로 최상위 노드에 도착하면 빠져나간다.
	}
	
}
//삭제 할 경우
int remove() {
	
	if (sz == 0)
		return 0;
	else {
		sz--;
		int result = arr[1];
		int i = 1, temp = 0;
		arr[1] = arr[sz+1];
		
        //자식 노드가 하나라도 존재한다면 while반복
		while (i * 2 <= sz) {
			temp = arr[i];
            //만약 오른쪽 자식 노드가 존재하고,  왼쪽 자식 노드보다 작다면 교환
                //이 경우는 반드시 부모 노드가 자식보다 크거나 같으므로 비교 필요X
			if (i * 2 + 1 <= sz && arr[i * 2] > arr[i * 2 + 1]) {
				arr[i] = arr[i * 2 + 1];
				arr[i * 2 + 1] = temp;
				i = i * 2 + 1;
			}
            //만약 왼쪽 자식 노드가 부모 노드보다 작다면 교환
			else if (arr[i * 2] < arr[i]) {
				arr[i] = arr[i * 2];
				arr[i * 2] = temp;
				i = i * 2;
			}
			else
				return result;
		}
		return result;
	}
}
int main() {
	
	int n,t;
	cin >> n;
	for (int i = 0; i < n; i++) {
		    cin >> t;
		    if (t == 0) {
		    	cout <<remove() << endl;
		    }
		    else {
		    	insert(t);
		    }
		}
	return 0;
}

1207koo 4년 전 2

39번째 줄이 잘못 되었습니다.

2 3

7 5 6 4

대충 이런 힙이 있을 때 1을 빼면 4가 1의 위치에 가고

2의 위치에 간 다음, 5<7이므로 5와 4가 위치가 바뀌고 4가 내려갑니다.

master1511 4년 전 0

아 제가 형제 노드를 생각 안한것같네요 감사합니다.

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

문제

문제

출처

ICPC

최소 힙 문제를 플었는데 어느 부분이 틀렸는지 모르겠습니다.

master1511 4년 전 1

1207koo 4년 전 2

master1511 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말