글 읽기 - 직접구현한 최대힙 한번만 봐주십쇼...

yousrain 4년 전 0

문제를 풀기 위해 문제에서 요구하는 부분만 구현했습니다.

간단하게 만든 만큼 오류가 없을 것 같은데 계속 틀렸습니다가 나와서

일단 stl 사용해서 풀었습니다만, 오류는 도저히 제 힘으로 못잡겠네요 ㅠㅠ

냉철한 진단 부탁드립니다.... ㅠㅠㅠㅠㅠㅠㅠ

#include<stdio.h>
typedef long long ll;
ll arr[800001]; // 인풋의 최대 사이즈가 10만이므로 최대 공간 40만으로 설정
int nod = 1; // 최댓값은 1로 설정하고, 배열의 1번자리부터 푸시를 시작합니다, nod는 들어갈 자리
int N, a;

void push(ll item);
ll pop();

int main(){
    scanf("%d", &N);
    while(N--){
	scanf("%lld", &a);
	if(a == 0) printf("%lld\n", pop());
	else push(a);
    }
    return 0;
}

void push(ll item){
    int i = nod++;            // 넣을 위치를 i에 저장
    arr[i] = item;            // item을 i위치에 넣습니다
    while(i > 1){             // 최대힙 구현을 위해 i가 1보다 클 동안만 반복
	if(arr[i] > arr[i/2]){    // 자신의 부모보다 크다면
	    ll swap = arr[i];     // 부모와 자신의 값을 바꾸고 
	    arr[i] = arr[i/2];
	    arr[i/2] = swap;
	    i /= 2;               // 부모로 옮겨 갑니다
	}
	else break;               // 부모보다도 크지 못하다면 반복을 종료합니다
    }
}

ll pop(){
    if(nod == 1) return 0;    // 들어갈 자리가 1임은 큐가 비었음을 말합니다
    else{
	ll ans = arr[1];          // 마지막에 리턴할 현대 최댓값을 ans에 저장합니다.
	int i = 1;                // 반복을 시작할 i를 1로 설정합니다.
	while(arr[i*2] != 0 || arr[i*2+1] != 0){    // 왼쪽 자식과 오른쪽 자식이 하나라도 0이 아니라면 반복 수행
	    if(arr[i*2] > arr[i*2+1]){    // 왼쪽 자식이 오른쪽 자식보다 크다면 부모와 왼쪽을 바꿉니다.
		arr[i] = arr[i*2];            
		i = i*2;                      // 그리고 왼쪽 자식으로 갑니다
	    }
	    else{                    // 반대로 오른쪽 자식이 왼쪽 자식보다 크다면 부모와 오른쪽을 바꿉니다
		arr[i] = arr[i*2+1];
		i = i*2+1;               // 그리고 오른쪽 자식으로 갑니다.
	    }
	}                            // 반복이 끝난 위치는 이제 빈 공간으로 간주합니다.
	arr[i] = arr[--nod];        // 가장 마지막에 들어간 item을 빈 공간에 넣어줍니다
	arr[nod] = 0;               // 빈공간에 넣어준 자리를 0으로 다시 바꿉니다
	while(i > 1){                // push 때와 같은 논리로 채워진 공간으로 올려 줍니다.
	    if(arr[i] > arr[i/2]){
		ll swap = arr[i];
		arr[i] = arr[i/2];
		arr[i/2] = swap;
		i /= 2;
	    }
	    else break;
	}
	return ans;                // 처음 저장했던 ans를 리턴합니다.
    }
}

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

문제

문제

출처

ICPC

직접구현한 최대힙 한번만 봐주십쇼...

yousrain 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말