글 읽기 - 50프로에서 막힙니다.

akqjqcjs7 3년 전 0

50%에서 막힙니다. 아무 값이나 넣어보고 해봤지만 어디에서 문제가 생기는지 도저히 모르겠습니다.

제 생각으로는 모든 방향에 대해 조건을 달았다고 생각하는데 무엇을 빼먹었는지를 잘 모르겠습니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<memory.h>
#include<stdbool.h>
int array[100001];
int size;
void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
//절대값 반환 함수
int juldae(int num) {

    num = num >= 0 ? num : (-1) * num;

    return num;
}
void insert(int data) {
    //인덱스는 사이즈다
    int idx = ++size;

    //인덱스가 1이 아니고 data의 절대값이 작거나 같으면 들어온다.
    while (idx != 1 && juldae(data) <= juldae(array[idx / 2])) {
        //비교하는 두수의 절대값이 같으면
        if (juldae(data) == juldae(array[idx / 2])) {
            //자식보다 같거나 작으면 바꿀 필요가없다.
            if (data >= array[idx / 2]) {
                break;
            }
        }
        //절대값이 자기(data)보다 큰 경우면 바로 여기로온다.
        array[idx] = array[idx / 2];
        idx /= 2;
    }

    array[idx] = data;
}
int delete() {
    if (!size) { return 0; }

    int data = array[1];
    array[1] = array[size--];
    
    int parent = 1;
    int child = 2;

    while (1) {
        //전체 크기를 벗어나면 탈출
        if (child > size) { break; }
        //오른쪽 절대값이 작다면 오른쪽 자식 인덱스
        if (child + 1 <= size && juldae(array[child]) > juldae(array[child + 1])) { child++; }
        //왼쪽 절대값과 오른쪽 절대값이 같다면
        if (child + 1 <= size && juldae(array[child]) == juldae(array[child + 1]) && array[child] > array[child + 1]) { child++; }

        //자식 절대값이 부모 절대값보다 크면 무조건 탈출
        if (juldae(array[child]) > juldae(array[parent])) { break; }
        //근데 만약 절대값이 같다면 진짜 크기를 비교
        if (juldae(array[child]) == juldae(array[parent]) && array[child] > array[parent]) { break; }

        swap(&array[child], &array[parent]);
        
        parent = child;
        child = parent * 2;
    }

    return data;
}
int main()
{
    int n;
    scanf("%d", &n);
    //int h = (int)ceil(log2(n));
    //array = (int*)malloc(sizeof(int) * (1 << h));

    for (int i = 0; i < n; i++) {
        int data;
        scanf("%d", &data);

        if (!data) { printf("%d\n", delete()); continue; }
        insert(data);
    }
    
    return 0;
}

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

문제

문제

출처

ICPC

50프로에서 막힙니다.

akqjqcjs7 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말