글 읽기 - (c언어) 계속 시간 초과가 뜨는데 이유 좀 알려주세요!!

oyhskw 5년 전 0

c언어로 구현했고, 계속 시간 초과가 뜨는데 왜 그런지 모르겠습니다.

이유를 알려주시면 정말정말 감사드리겠습니다.!!

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct deque{
	int front, back;
	int count;
	int size;
	int *content;
};

int empty(struct deque *deq){
	if(deq->count==0) return 1;
	else return 0;
}

int full(struct deque *deq){
	if(deq->count==deq->size) return 1;
	else return 0;
}

int front(struct deque *deq){
	if(!empty(deq)) return deq->content[deq->front];
	else return -1;
}

int back(struct deque *deq){
	if(!empty(deq)) return deq->content[deq->back];
	else return -1;
}

void push_front(struct deque *deq, int num){
	if(!full(deq)){
		if(deq->count==0){
			deq->front=0;
			deq->back=0;
		}else{
			if(deq->front==0) deq->front=deq->size-1;
			else deq->front--;
		}
			
		deq->content[deq->front]=num;
		deq->count++;
		
	}
}

void push_back(struct deque *deq, int num){
	if(!full(deq)){
		if(deq->count==0){
			deq->front=0;
			deq->back=0;
		}else{	
			deq->back=(deq->back+1)%deq->size;
		}
		
		deq->content[deq->back]=num;
		deq->count++;

	}
}

int pop_front(struct deque *deq){
	int temp;
	if(empty(deq)) return -1;
	else{
		temp=deq->content[deq->front];
		deq->front=(deq->front+1)%deq->size;
		deq->count--;
		return temp;
	} 
}


int pop_back(struct deque *deq){
	int temp;
	if(empty(deq)) return -1;
	else{
		temp=deq->content[deq->back];
		if(deq->back==0) deq->back=deq->size-1;
		else deq->back--;
		deq->count--;
		return temp;
	}
}

void init(struct deque *deq, int bound){
	deq->front=0;
	deq->back=0;
	deq->count=0;
	deq->size=bound;
}

int find_index(struct deque *deq, int wated){
	int i;
	for(i=0; i<deq->size; i++){
		if(deq->content[i]==wated){
			return i;
		}
	}
	return -1;
}

int count_oper(struct deque *deq, int wated){
	int differ1, differ2;
	int index;
    int sum=0;
    
	index=find_index(deq, wated);	
	differ1=abs(index-deq->front);
	differ2=abs(index-deq->back);

	if(differ1<differ2){ //operation 2
		while(front(deq)!=wated){
			push_back(deq, pop_front(deq));
			sum++;
		}
	}else{ //opertion 3
		while(front(deq)!=wated){
			push_front(deq, pop_back(deq));
			sum++;
		}
	}

	pop_front(deq); //opertion 1
    return sum;
}

int main(){
	int deque_size, times;
	struct deque *deq=malloc(sizeof(struct deque));
	int i;
	int wated;
	int sum=0;

	scanf("%d %d", &deque_size, &times);
	
	init(deq, deque_size);
	deq->content=malloc(sizeof(int)*deque_size);
    
	for(i=0; i<deque_size; i++){
		push_back(deq, i+1);
	}

	for(i=0; i<times; i++){
		scanf("%d", &wated);
        sum=sum+count_oper(deq, wated-1);
	}
    
	printf("%d\n",sum);

	free(deq->content);
	free(deq);
	return 0;
	
}

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

문제

문제

출처

ICPC

(c언어) 계속 시간 초과가 뜨는데 이유 좀 알려주세요!!

oyhskw 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말