글 읽기 - (C) 이중 우선순위 큐 min-max heap 시간초과

tongkath 2년 전 0

질문게시판에서 이중우선순위 큐는

min-max heap을 이용해 푸는 것이 최고라는 것을 본 저는

영문위키를 보며 어찌어찌 비슷하게는 만들어 냈으나

계속 시간초과가 납니다

미천한 제 실력으로는 어디를 고쳐야 시간을 줄일 수 있을지 모르겠어

시간초과가 안되게 하는법에 대한 조언을 여쭙고자 합니다

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#7662
int heap[1000010]={0};
int valid[1000010]={0};//문제조건상 힙에 존재하지 않음을 0으로 표시할 수 없기때문에 추가
int size=0;
void swap(int,int);
void makeheap();
void delete_min();
void delete_max();
void insert(int);
void heapify(int);
void max_heapify(int);
void min_heapify(int);
void push_up(int);
void push_up_min(int);
void push_up_max(int);
int get_minNode(int);
int get_maxNode(int);
void deleteAll();
void print(){
    for(int i=0;i<size;i++){
        printf("%d ",heap[i+1]);
    }
};
int main(void){
    int T,Q;
    int cmd;
    char ID;
    
    scanf("%d",&T);
    for(int i=0;i<T;i++){
        getchar();
        scanf("%d",&Q);
        for(int j=0;j<Q;j++){
            getchar();
            scanf("%c",&ID);
            if(ID=='I'){
                scanf("%d",&cmd);
                insert(cmd);
            }
            else if(ID=='D'){
                scanf("%d",&cmd);
                if(cmd==1)delete_max();
                else if(cmd==-1)delete_min();
                //print();
            }
        }
        if(size==0)printf("EMPTY\n");
        else printf("%d %d\n",heap[size],heap[1]);
        deleteAll();
    }
    return 0;
}
void swap(int a, int b){
    int temp;
    temp=heap[a];
    heap[a]=heap[b];
    heap[b]=temp;
}
void makeheap(){//힙이 아닌 상태의 배열을 힙으로 만드는 함수
    for(int i=size/2;i>0;i++){//size/2부터 1까지인 이유는 그에 해당하는 노드들이 자식을 갖고 있는 노드임
        heapify(i);
    }
}
void delete_min(){
    if(size==0)return;
    heap[1]=heap[size];//맨 위 노드를 삭제하며 맨 끝 노드를 맨위로 옮기고
    heap[size]=0;
    valid[size]=0;
    size--;
    heapify(1);//다시 최소최대힙으로 만든다
}
void delete_max(){
    if(size==0)return;
    if(size==1){
        valid[1]=0;
        heap[1]=0;
        size--;
        return;
    }
    int bigger;
    if(heap[2]<heap[3])bigger=3;
    else bigger=2;
    heap[bigger]=heap[size];
    valid[size]=0;
    size--;
    heapify(bigger);
}
void insert(int n){
    size++;
    heap[size]=n;//힙 제일 마지막 노드에 넣고
    valid[size]=1;
    push_up(size);//비교하며 위로 올린다
}
void push_up(int i){
    if(i!=1){
        if((int)log2(i)%2==0){
            if(heap[i] > heap[i/2]){
                swap(i,i/2);
                push_up_max(i/2);//부모노드 자리로 올라간 i를 더 비교하며 올린다
            }
            else push_up_min(i);
        }
        else{
            if(heap[i] < heap[i/2]){
                swap(i,i/2);
                push_up_min(i/2);
            }
            else push_up_max(i);
        }
    }
}
void push_up_min(int i){
    if(i/4>0 && heap[i] < heap[i/4]){//grandparent노드와 비교
        swap(i,i/4);
        push_up_min(i/4);
    }
}
void push_up_max(int i){
    if(i/4>0 && heap[i] > heap[i/4]){
        swap(i,i/4);
        push_up_max(i/4);
    }
}
void heapify(int i){
    if((int)log2(i)%2)max_heapify(i);
    else min_heapify(i);//짝수면 min레벨
}
void max_heapify(int i){
    if(valid[i*2]){//현재 노드가 자식을 갖고있으면
        int m=get_maxNode(i);
        if(m >= (i*4) && m <= (i*8)-1){//m이 grandchild인 경우
            swap(i,m);
            if(heap[m] > heap[m/2]){//i가 m위치로 간 이후 그것의 부모보다 크면 
                swap(m,m/2);
            }
            max_heapify(m);
        }
        else if(m==i+1 || m==i+2)swap(m,i);
    }
}
void min_heapify(int i){
    if(valid[i*2]){//현재 노드가 자식을 갖고있으면
        int m=get_minNode(i);
        if(m >= (i*4) && m <= (i*8)-1){//m이 grandchild인 경우
            swap(i,m);
            if(heap[m] > heap[m/2]){//i가 m위치로 간 이후 그것의 부모보다 크면 
                swap(m,m/2);
            }
            min_heapify(m);
        }
        else if(m==i+1 || m==i+2)swap(m,i);
    } 
}
int get_minNode(int i){
    int min=i;//다 비교를 해도 안바뀌면 현재노드가 제일 작은것
    if(heap[(i*2)] < heap[min])min=i*2;
    if(valid[(i*2)+1] && heap[(i*2)+1] < heap[min])min=(i*2)+1;//자식노드비교
    
    for(int j=0;j<i*2;j++){//grandchildren 비교
        if(valid[(i*4)+j]==0)break;
        if(heap[(i*4)+j] < heap[min])min=(i*4)+j;
    }
    return min;
}
int get_maxNode(int i){
    int max=i;//다 비교를 해도 안바뀌면 현재노드가 제일 큰것
    if(heap[(i*2)] > heap[max])max=i*2;
    if(valid[(i*2)+1] && heap[(i*2)+1] > heap[max])max=(i*2)+1;//자식노드비교

    for(int j=0;j<i*2;j++){
        if(valid[(i*4)+j]==0)break;
        if(heap[(i*4)+j] > heap[max])max=(i*4)+j;
    }
    return max;
}
void deleteAll(){
    int k=size;
    if(size==0)return;
    while(k--){
        delete_min();
    }
}

some256 2년 전 0

시간 초과가 발생하는 이유는 모르겠지만 반례입니다...

% Input
12
14
I 20
I 29
I -77
I -72
D -1
I 40
D 1
D -1
I -20
D -1
I -13
I -55
D -1
D -1
11
D 1
I 55
D -1
I 3
D 1
D -1
D -1
D 1
I 52
I 50
I 18
14
D -1
D -1
I -5
I 91
D 1
I 69
D 1
I -58
I 62
I 24
D -1
D 1
D 1
I -29
12
D -1
I -27
D -1
D 1
I -33
I -44
I -10
D 1
I 41
I 30
D 1
I 59
12
I 93
I 0
D 1
I -3
D -1
D -1
I 46
I -26
I 79
D -1
D 1
D 1
12
I -9
D 1
I 51
I -26
D -1
D 1
I 62
D 1
D -1
D -1
D 1
D -1
11
D 1
D -1
D 1
I 69
D -1
D -1
I -6
D -1
D 1
I -100
I 88
8
I -96
I 79
I 78
I -45
D -1
I -99
D 1
D 1
4
I -6
I 31
D -1
D 1
7
D 1
I 34
D -1
I -82
I 37
I -78
I -42
5
I -18
I 4
D 1
I 42
I 67
14
D -1
I 91
I 74
I -45
I -31
I -46
I -64
I 36
D 1
D -1
I -46
I 45
I 64
D 1

% What was actually got
29 20
50 18
-5 -29
30 -44
EMPTY
EMPTY
88 -100
-45 -99
EMPTY
-42 -82
67 -18
45 -46


% What was expected
29 20
52 18
-5 -29
59 -44
EMPTY
EMPTY
88 -100
-45 -99
EMPTY
37 -82
67 -18
64 -46

tongkath 2년 전 0

감사합니다 ! 덕분에 문제를 발견했습니다만..

기존코드의 50-51번째 줄을 다음과 같이 고쳤습니다.

올려주신 반례들은 잘 통과하지만 시간초과는 그대로네요 ㅜㅜ

if(size==0)printf("EMPTY\n");
else {
    int max;
    if(size==1)max=1;
    else if(size==2)max=2;
    else if(size > 2){
        if(heap[2]>heap[3])max=2;
        else max=3;
    }
    printf("%d %d\n",heap[max],heap[1]);
}

some256 2년 전 1

50-51 줄을 고쳐도 반례가 있습니다.

% Input
18
13
I -47
I -2147483648
I 2147483647
I -45
I -2147483648
D 1
D -1
D 1
D 1
D 1
D 1
I 2147483647
D 1
7
I -60
I 2147483647
I 2147483647
D -1
I -92
I 0
D -1
10
I -2147483648
D -1
I 2147483647
D 1
D -1
D 1
I 2147483647
I 2147483647
I -2147483648
D -1
7
I 2147483647
D 1
D -1
D -1
I 2147483647
D -1
I -61
4
D 1
D 1
D 1
I 20
16
D 1
D -1
D -1
I 53
I -19
I -2147483648
I -2147483648
D 1
I 2147483647
D 1
I -2147483648
D 1
I -82
D -1
D 1
D -1
8
D -1
D -1
D -1
I 26
I 2147483647
I 2147483647
I -2147483648
I 75
11
D 1
D -1
D 1
I 2147483647
I 2147483647
I 38
I -2147483648
I -2147483648
I 58
I 64
D 1
12
I 2147483647
I 2147483647
I 2147483647
I -2147483648
I -62
I 43
D 1
I -2147483648
D -1
I 2147483647
D -1
D 1
12
I 2147483647
D 1
I 64
D -1
D 1
I 63
I -30
D -1
I 53
I 25
D 1
D -1
10
I 89
I 2147483647
D -1
D -1
D 1
D 1
I 2147483647
I -53
D -1
I -2147483648
17
I -44
I -58
I 2147483647
I 2147483647
D 1
D -1
I 2147483647
I 3
I 2147483647
I -2147483648
I 80
I -32
D 1
I -11
I 19
D 1
D 1
10
I -2147483648
I 2147483647
D -1
D 1
I 18
I 2147483647
D -1
D -1
I 2147483647
D -1
13
I -2147483648
D -1
I -2147483648
D 1
D -1
I 100
I -2147483648
I 48
I 78
I 2147483647
D -1
I 2147483647
D -1
7
I -2147483648
I 75
D -1
I 2147483647
I 2147483647
I 18
D 1
5
I 8
I -77
D 1
I -2147483648
I -25
11
D 1
D -1
D 1
D -1
D -1
D 1
D -1
I -2147483648
D -1
D 1
D -1
12
I -2147483648
I -2147483648
D -1
I 44
I 2147483647
D -1
I 80
I -28
I 2147483647
D 1
D 1
D -1

% What was actually got
EMPTY
2147483647 0
2147483647 2147483647
-61 -61
20 20
-2147483648 -2147483648
2147483647 -2147483648
2147483647 -2147483648
2147483647 -62
53 53
2147483647 -2147483648
3 -2147483648
EMPTY
2147483647 78
2147483647 18
-25 -2147483648
EMPTY
80 44


% What was expected
EMPTY
2147483647 0
2147483647 2147483647
-61 -61
20 20
-2147483648 -2147483648
2147483647 -2147483648
2147483647 -2147483648
2147483647 -62
53 53
2147483647 -2147483648
80 -2147483648
EMPTY
2147483647 78
2147483647 18
-25 -2147483648
EMPTY
80 44

tongkath 2년 전 0

다시금 감사합니다 !!

몇 군데 다시 수정하니

작성해주신 테스트케이스들은 잘되네요.

그럼에도 시간초과가 아니라 틀렸습니다...가 뜨는 것은 또 반례가 있다는 것이겠죠? ㅜㅜ

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#7662
int heap[1000010]={0};
int valid[1000010]={0};//문제조건상 힙에 존재하지 않음을 0으로 표시할 수 없기때문에 추가
int size=0;
void swap(int,int);
void makeheap();
void delete_min();
void delete_max();
void insert(int);
void heapify(int);
void max_heapify(int);
void min_heapify(int);
void push_up(int);
void push_up_min(int);
void push_up_max(int);
int get_minNode(int);
int get_maxNode(int);
void deleteAll();
void print(){
    printf("\n");
    for(int i=0;i<size;i++){
        printf("%d ",heap[i+1]);
    }
};
int main(void){
    int T,Q;
    int cmd;
    char ID;
    
    scanf("%d",&T);
    for(int i=0;i<T;i++){
        getchar();
        scanf("%d",&Q);
        for(int j=0;j<Q;j++){
            getchar();
            scanf("%c",&ID);
            if(ID=='I'){
                scanf("%d",&cmd);
                insert(cmd);
            }
            else if(ID=='D'){
                scanf("%d",&cmd);
                if(cmd==1)delete_max();
                else if(cmd==-1)delete_min();
            }
            //print();
        }
        if(size==0)printf("EMPTY\n");
        else {
            int max;
            if(size==1)max=1;
            else if(size==2)max=2;
            else if(size > 2){
                if(heap[2]>heap[3])max=2;
                else max=3;
            }
            printf("%d %d\n",heap[max],heap[1]);
        }
        deleteAll();
    }
    return 0;
}
void swap(int a, int b){
    int temp;
    temp=heap[a];
    heap[a]=heap[b];
    heap[b]=temp;
}
void makeheap(){//힙이 아닌 상태의 배열을 힙으로 만드는 함수
    for(int i=size/2;i>0;i++){//size/2부터 1까지인 이유는 그에 해당하는 노드들이 자식을 갖고 있는 노드임
        heapify(i);
    }
}
void delete_min(){
    if(size==0)return;
    heap[1]=heap[size];//맨 위 노드를 삭제하며 맨 끝 노드를 맨위로 옮기고
    heap[size]=0;
    valid[size]=0;
    size--;
    if(size!=0)heapify(1);//다시 최소최대힙으로 만든다
}
void delete_max(){
    if(size==0)return;
    if(size==1){
        valid[1]=0;
        heap[1]=0;
        size--;
        return;
    }
    if(size==2){
        valid[2]=0;
        heap[2]=0;
        size--;
        return;
    }
    int bigger;
    if(heap[2]<heap[3])bigger=3;
    else bigger=2;
    heap[bigger]=heap[size];
    valid[size]=0;
    size--;
    heapify(bigger);
}
void insert(int n){
    size++;
    heap[size]=n;//힙 제일 마지막 노드에 넣고
    valid[size]=1;
    push_up(size);//비교하며 위로 올린다
}
void push_up(int i){
    if(i!=1){
        if((int)log2(i)%2==0){
            if(heap[i] > heap[i/2]){
                swap(i,i/2);
                push_up_max(i/2);//부모노드 자리로 올라간 i를 더 비교하며 올린다
            }
            else push_up_min(i);
        }
        else{
            if(heap[i] < heap[i/2]){
                swap(i,i/2);
                push_up_min(i/2);
            }
            else push_up_max(i);
        }
    }
}
void push_up_min(int i){
    if(i/4>0 && heap[i] < heap[i/4]){//grandparent노드와 비교
        swap(i,i/4);
        push_up_min(i/4);
    }
}
void push_up_max(int i){
    if(i/4>0 && heap[i] > heap[i/4]){
        swap(i,i/4);
        push_up_max(i/4);
    }
}
void heapify(int i){
    if((int)log2(i)%2)max_heapify(i);
    else min_heapify(i);//짝수면 min레벨
}
void max_heapify(int i){
    if(valid[i*2]){//현재 노드가 자식을 갖고있으면
        int m=get_maxNode(i);
        if(m >= (i*4) && m <= (i*4)+3){//m이 grandchild인 경우
            swap(i,m);
            if(heap[m] > heap[m/2]){//i가 m위치로 간 이후 그것의 부모보다 크면 
                swap(m,m/2);
            }
            max_heapify(m);
        }
        else if(m==i*2 || m==(i*2)+1)swap(m,i);
    }
}
void min_heapify(int i){
    if(valid[i*2]){//현재 노드가 자식을 갖고있으면
        int m=get_minNode(i);
        if(m >= (i*4) && m <= (i*4)+3){//m이 grandchild인 경우
            swap(i,m);
            if(heap[m] > heap[m/2]){//i가 m위치로 간 이후 그것의 부모보다 크면 
                swap(m,m/2);
            }
            min_heapify(m);
        }
        else if(m==i*2 || m==(i*2)+1)swap(m,i);
    } 
}
int get_minNode(int i){
    int min=i;//다 비교를 해도 안바뀌면 현재노드가 제일 작은것
    if(heap[(i*2)] < heap[min])min=i*2;
    if(valid[(i*2)+1] && heap[(i*2)+1] < heap[min])min=(i*2)+1;//자식노드비교
    
    for(int j=0;j<4;j++){//grandchildren 비교
        if(valid[(i*4)+j]==0)break;
        if(heap[(i*4)+j] < heap[min])min=(i*4)+j;
    }
    return min;
}
int get_maxNode(int i){
    int max=i;//다 비교를 해도 안바뀌면 현재노드가 제일 큰것
    if(heap[(i*2)] > heap[max])max=i*2;
    if(valid[(i*2)+1] && heap[(i*2)+1] > heap[max])max=(i*2)+1;//자식노드비교

    for(int j=0;j<4;j++){
        if(valid[(i*4)+j]==0)break;
        if(heap[(i*4)+j] > heap[max])max=(i*4)+j;
    }
    return max;
}
void deleteAll(){
    int k=size;
    if(size==0)return;
    while(k--){
        delete_min();
    }
}