글 읽기 - 코드 두번 확인했습니다.. 고수님들의 도움이 절실합니다..

cdt416z 4년 전 0

47퍼에서 틀리는데 어디서 틀린지 모르겠네요 ㅠㅠ

반례도 적어서 코드 천천히 확인도 했는데

논리적으로 틀린 부분도 없는거같습니다

부탁드립니다..

#include <stdio.h>

int heap[100002] = { 0 };
int index = 0;

int abs(int a){
    return a > 0 ? a : -1 * a;
}

void push(int num){
    heap[++index] = num;
    for(int i = index; i > 1;){
        if(abs(heap[i]) < abs(heap[i / 2])){
        	int temp = heap[i];
        	heap[i] = heap[i / 2];
        	heap[i / 2] = temp;
            i /= 2;
        }
        else if(abs(heap[i]) == abs(heap[i / 2]) && heap[i] < heap[i / 2]){
        	int temp = heap[i];
        	heap[i] = heap[i / 2];
        	heap[i / 2] = temp;
            i /= 2;
        }
        else{
            break;
        }
    }
}

int pop(){
    int ret = heap[1];
    heap[1] = heap[index];
    heap[index--] = 0;
    for(int i = 1; i * 2 <= index;){
        if(i * 2 + 1 > index){
            if(abs(heap[i]) < abs(heap[i * 2])){
                ;
            }
            else if(abs(heap[i]) == abs(heap[i * 2])){
                if(heap[i] > heap[i * 2]){
                    int temp = heap[i];
                    heap[i] = heap[i * 2];
                    heap[i * 2] = temp;
                }
            }
            else{
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
            }
            break;
        }
        if(abs(heap[i]) < abs(heap[i * 2]) && abs(heap[i]) < abs(heap[i * 2 + 1])){
            break;
        }
        else if(abs(heap[i]) == abs(heap[i * 2]) && abs(heap[i]) == abs(heap[i * 2 + 1])){
            if(heap[i] <= heap[i * 2] && heap[i] <= heap[i * 2 + 1]){
                break;
            }
            else if(heap[i] <= heap[i * 2]){
                int temp = heap[i];
                heap[i] = heap[i * 2 + 1];
                heap[i * 2 + 1] = temp;
                i = i * 2 + 1;
            }
            else if(heap[i] <= heap[i * 2 + 1]){
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
                i = i * 2;
            }
            else{
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
                i = i * 2;
            }
        }
        else if(abs(heap[i]) == abs(heap[i * 2])){
            int temp = heap[i];
            heap[i] = heap[i * 2 + 1];
            heap[i * 2 + 1] = temp;
            i = i * 2 + 1;
        }
        else if(abs(heap[i]) == abs(heap[i * 2 + 1])){
            int temp = heap[i];
            heap[i] = heap[i * 2];
            heap[i * 2] = temp;
            i = i * 2;
        }
        else{
            if(abs(heap[i * 2]) > abs(heap[i * 2 + 1])){
                int temp = heap[i];
                heap[i] = heap[i * 2 + 1];
                heap[i * 2 + 1] = temp;
                i = i * 2 + 1;
            }
            else if(abs(heap[i * 2]) < abs(heap[i * 2 + 1])){
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
                i = i * 2;
            }
            else{
                if(heap[i * 2] > heap[i * 2 + 1]){
                    int temp = heap[i];
                    heap[i] = heap[i * 2 + 1];
                    heap[i * 2 + 1] = temp;
                    i = i * 2 + 1;
                }
                else{
                    int temp = heap[i];
                    heap[i] = heap[i * 2];
                    heap[i * 2] = temp;
                    i = i * 2;
                }
            }
        }
    }
    return ret;
}

int main(){
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        int a;
        scanf("%d", &a);
        if(a == 0){
           printf("%d\n", index == 0 ? 0 : pop());
        }
        else{
            push(a);
        }
    }
    return 0;
}

cdt416z 4년 전 0

57 ~ 94번 줄의 코드를 빼먹었네요

거기다가 swap할때 하나를 잘못 써서 그거때문에 1시간 반 날렸습니다..

swap 함수의 필요성을 느낀 문제였네요

다 풀어놓고 고생하지맙시다..

#include <stdio.h>

int heap[100002] = { 0 };
int index = 0;

int abs(int a){
    return a > 0 ? a : -1 * a;
}

void push(int num){
    heap[++index] = num;
    for(int i = index; i > 1;){
        if(abs(heap[i]) < abs(heap[i / 2])){
        	int temp = heap[i];
        	heap[i] = heap[i / 2];
        	heap[i / 2] = temp;
            i /= 2;
        }
        else if(abs(heap[i]) == abs(heap[i / 2]) && heap[i] < heap[i / 2]){
        	int temp = heap[i];
        	heap[i] = heap[i / 2];
        	heap[i / 2] = temp;
            i /= 2;
        }
        else{
            break;
        }
    }
}

int pop(){
    int ret = heap[1];
    heap[1] = heap[index];
    heap[index--] = 0;
    for(int i = 1; i * 2 <= index;){
        if(i * 2 + 1 > index){
            if(abs(heap[i]) < abs(heap[i * 2])){
                ;
            }
            else if(abs(heap[i]) == abs(heap[i * 2])){
                if(heap[i] > heap[i * 2]){
                    int temp = heap[i];
                    heap[i] = heap[i * 2];
                    heap[i * 2] = temp;
                }
            }
            else if(abs(heap[i]) > abs(heap[i * 2])){
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
            }
            break;
        }
        if(abs(heap[i]) < abs(heap[i * 2]) && abs(heap[i]) < abs(heap[i * 2 + 1])){
            break;
        }
        else if(abs(heap[i]) < abs(heap[i * 2])){
            if(abs(heap[i]) == abs(heap[i * 2 + 1])){
                if(heap[i] > heap[i * 2 + 1]){
                    int temp = heap[i];
                    heap[i] = heap[i * 2 + 1];
                    heap[i * 2 + 1] = temp;
                    i = i * 2 + 1;
                }
                else{
                    break;
                }
            }
            else if(abs(heap[i]) > abs(heap[i * 2 + 1])){
                int temp = heap[i];
                heap[i] = heap[i * 2 + 1];
                heap[i * 2 + 1] = temp;
                i = i * 2 + 1;
            }
        }
        else if(abs(heap[i]) < abs(heap[i * 2 + 1])){
            if(abs(heap[i]) == abs(heap[i * 2])){
                if(heap[i] > heap[i * 2]){
                    int temp = heap[i];
                    heap[i] = heap[i * 2];
                    heap[i * 2] = temp;
                    i = i * 2;
                }
                else{
                    break;
                }
            }
            else if(abs(heap[i]) > abs(heap[i * 2])){
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
                i = i * 2;
            }
        }
        else if(abs(heap[i]) == abs(heap[i * 2]) && abs(heap[i]) == abs(heap[i * 2 + 1])){
            if(heap[i] <= heap[i * 2] && heap[i] <= heap[i * 2 + 1]){
                break;
            }
            else if(heap[i] <= heap[i * 2]){
                int temp = heap[i];
                heap[i] = heap[i * 2 + 1];
                heap[i * 2 + 1] = temp;
                i = i * 2 + 1;
            }
            else if(heap[i] <= heap[i * 2 + 1]){
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
                i = i * 2;
            }
            else{
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
                i = i * 2;
            }
        }
        else if(abs(heap[i]) == abs(heap[i * 2])){
            int temp = heap[i];
            heap[i] = heap[i * 2 + 1];
            heap[i * 2 + 1] = temp;
            i = i * 2 + 1;
        }
        else if(abs(heap[i]) == abs(heap[i * 2 + 1])){
            int temp = heap[i];
            heap[i] = heap[i * 2];
            heap[i * 2] = temp;
            i = i * 2;
        }
        else{
            if(abs(heap[i * 2]) > abs(heap[i * 2 + 1])){
                int temp = heap[i];
                heap[i] = heap[i * 2 + 1];
                heap[i * 2 + 1] = temp;
                i = i * 2 + 1;
            }
            else if(abs(heap[i * 2]) < abs(heap[i * 2 + 1])){
                int temp = heap[i];
                heap[i] = heap[i * 2];
                heap[i * 2] = temp;
                i = i * 2;
            }
            else{
                if(heap[i * 2] > heap[i * 2 + 1]){
                    int temp = heap[i];
                    heap[i] = heap[i * 2 + 1];
                    heap[i * 2 + 1] = temp;
                    i = i * 2 + 1;
                }
                else{
                    int temp = heap[i];
                    heap[i] = heap[i * 2];
                    heap[i * 2] = temp;
                    i = i * 2;
                }
            }
        }
    }
    return ret;
}

int main(){
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        int a;
        scanf("%d", &a);
        if(a == 0){
            if(index == 0){
                printf("0\n");
            }
            else{
                printf("%d\n", pop());
            }
        }
        else{
            push(a);
        }
    }
    return 0;
}

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

문제

문제

출처

ICPC

코드 두번 확인했습니다.. 고수님들의 도움이 절실합니다..

cdt416z 4년 전 0

cdt416z 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말