글 읽기 - 시간초과 질문이요

hoon3722 4년 전 0

입력 0 1 해도 시간초과나는거보니 굉장히 단순한 실수 한 것 같은데 못찾겠어요..

뭘 잘못쓴거죠?

#include <stdio.h>
#include <iostream>
#include <queue>
#define max 100000
using namespace std;

typedef struct{
    
    int key;
    
}element;

typedef struct{
    
    element heap[max];
    int heap_size; 
    
}heaptype;

heaptype h;

void push(int item){

    int i;
    i=++h.heap_size;
    h.heap[i].key=item;
    
    while(i!=1 && item > h.heap[i/2].key){
        
        h.heap[i].key=h.heap[i/2].key;
        
        i=i/2;
    }
    
    h.heap[i].key=item;
    
}

int pop(){
    
    int p,c;
    int item,temp;
    
    item=h.heap[1].key;
    temp=h.heap[h.heap_size--].key;
    
    p=1;
    c=2;
    
    while(c<=h.heap_size){
        
        if( (c<h.heap_size) && (h.heap[c].key < h.heap[c+1].key))
            c++;
            
        if(temp>h.heap[c].key)
            break;
        
        h.heap[p].key=h.heap[c].key;
        p=c;
        c*=2;
            
        
    }
    h.heap[p].key=temp;
    return item;
}


int main()
{
    int k,t,i;
    queue <int> q;
    h.heap_size=0;
    
    scanf("%d",&k);
    
    for(i=1;i<=k;k++){
        
        scanf("%d",&t);
        q.push(t);
    }
    
    while(!q.empty()){
        
        if(q.front()==0){
            
            if(h.heap_size==0)
                printf("0\n");
            else
                printf("%d\n",pop());
        }
        
        else{
            
            push(q.front());
            
        }
        
        q.pop();
    }
    return 0;
}

wpqldmlrna 4년 전 1

77번째 줄

for (i = 1; i <= k; k++) {

scanf("%d", &t);
q.push(t);
}

에서 i 가 아닌 k 값을 ++ 해주기 때문에 입력을 무한히 받습니다.

따라서 진행이 되지 못하고 시간초과가 발생합니다.

hoon3722 4년 전 0

감사합니다 근데 제가 포인터 변수도 안써서 그냥 풀었는데 왜 풀리는지 잘 모르겠습니다.

혹시 구조체 변수의 멤버들은 전역변수 같은 것 이라서 계속 어느 함수를 가던 값도 유지되는것인가요??

hoon3722 4년 전 0

아 그리고 이번에는 포인터 써서 풀었는데 22행에 2번째인자 element item.key 랑 90행에 2번째인자 q.front()에 오류뜨면서 계속 안되는데 왜 안되는지 잘 모르겠습니다.

구조체 첨 써보는데 너무 까다롭네요..

#include <stdio.h>
#include <iostream>
#include <queue>
#define max 100000
using namespace std;

typedef struct{
    
    int key;
    
}element;

typedef struct{
    
    element heap[max];
    int heap_size; 
    
}heaptype;

heaptype h2;

void push(heaptype *h,element item.key){
    
    int i;
    i=++(h->heap_size);
    
    while((i!=1) && (h->heap[i/2].key<item.key)){
        
        h->heap[i].key=h->heap[i/2].key;
        i/=2;
        
    }
    
    h->heap[i].key=item.key;
}

int pop(heaptype *h){
    
    element item,temp;
    int p,c;
    
    temp.key=h->heap[1].key;
    item.key=h->heap[(h->heap_size)--].key;
    p=1;
    c=2;
    
    while(c<=h->heap_size){
        
        if(c<h->heap_size && h->heap[c].key < h->heap[c+1].key)
            c++;
            
        if(item.key > h->heap[c].key)
            break;
        
        h->heap[p].key=h->heap[c].key;
        p=c;
        c*=2;
    }
    
    h->heap[p].key=item.key;
    
    return temp.key;
}

int main(){
    
    int t,k,i;
    
    queue<int> q;
    
    scanf("%d",&t);
    
    for(i=1;i<=t;i++){
        
        scanf("%d",&k);
        q.push(k);
    }
    
    while(!q.empty()){
        
        if(q.front()==0){
            
            if(h2.heap_size==0)
                printf("0\n");
            else
                printf("%d\n",pop(&h2));
            
        }
        else
            push(&h2,q.front());
        
        q.pop();
    }
    
    return 0;
}

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

문제

문제

출처

ICPC

시간초과 질문이요

hoon3722 4년 전 0

wpqldmlrna 4년 전 1

hoon3722 4년 전 0

hoon3722 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말