글 읽기 - 시간초과가 나오는 이유를 모르겠습니다 도와주세요ㅠㅠ

siriusbug257 1년 전 0

시간초과가 나오는 이유를 모르겠습니다 도와주세요ㅠㅠ

#include <stdio.h>
#include <string.h>

int main()
{
    int n=0;
    scanf("%d", &n);
    float numbers[27];
    char command[101];
    int len=0;
    scanf("%s", command);
    len=strlen(command);
    for(int i=0; i<n; i++)
    {
        scanf("%f", &numbers[i]);
    }
    // printf("%d\n", len);

    float result=0;
    result=numbers[0];
    int numtocal=0;
    int flag=0;
    flag=1;
    for(int i=1; i<len; i++)
    {
        // printf("%.2f\t", result);
        if(command[i]>=65)
        {
            numtocal++;
        }
        if(command[i]=='+' || command[i]=='-')
        {   
            float temp=0;
            int k=0;
            int realflag=i-numtocal*2+1;
            temp=numbers[command[realflag]-65];
            k++;
            while(k<numtocal)
            {
                if(command[i-k]=='*')
                {
                    temp*=numbers[command[++realflag]-65];
                    k++;
                }
                else if(command[i-k]=='/')
                {
                    temp/=numbers[command[++realflag]-65];
                    k++;
                }
            }
            if(command[i]=='+')
            {
                // printf("%f\n", temp);
                result+=temp;
                temp=0;
                k=0;
                numtocal=0;
                
            }
            else if(command[i]=='-')
            {
                // printf("%f\n", temp);
                result-=temp;
                temp=0;
                k=0;
                numtocal=0;
                
            }
        }
    }
    printf("%.2f", result);

    return 0;
    
}

byeongkeunahn 1년 전 1

numtocal은 현재 위치까지 나타난 A-Z의 개수를 모두 더한 값으로 위치에 의해서만 결정되며 중간 계산과정의 영향을 받지 않습니다.

코드의 문제 중 하나는 더하기나 빼기가 나오면 그 전에 나온 모든 연산자가 곱하기나 나누기였을 것이라고 가정하는데, 이 가정은 맞지 않습니다. 따라서, 더하기 다음에 더하기가 나오면 앞으로 가도 곱하기나 나누기를 찾을 수 없기 때문에 38번 줄의 조건이 만족되지 않은 채로 무한 루프가 발생합니다.

다른 문제는 후위 표기법에서는 사칙연산의 우선순위를 고려할 필요가 없다는 점입니다.

이 문제는 보편적으로 스택으로 푸는 문제입니다. 참고 바랍니다.

steve193 1년 전 1

스텍과 큐를 남겨두고 갑니다...

위에 큐와 스텍을 이용해서 푸시면 편합니다.

#include <stdio.h>
#include <string.h>
#define MAX_data_size 100
struct queue {
	int front;
	int rear;
	char data[MAX_data_size];
};
struct stack {
	int top;
	double data[MAX_data_size];
};
void init_queue(struct queue *q) {
	q->front = q->rear = 0;
	memset(q->data, 0, MAX_data_size);
}
int is_queue_empty(struct queue *q) {
	if (q->front == q->rear) return 1;
	return 0;
}
int is_queue_full(struct queue *q) {
	if (((q->rear + 1) % MAX_data_size) == q->front) return 1;
	return 0;
}
int enqueue(struct queue *q, char data) {
	if (is_queue_full(q)) return -1;
	q->rear = (q->rear + 1) % MAX_data_size;
	q->data[q->rear] = data;
	return 1;
}
char dequeue(struct queue *q) {
	if (is_queue_empty(q)) return -1;
	q->front = (q->front + 1) %	MAX_data_size;
	return q->data[q->front];
}
void init_stack(struct stack *s) {
	s->top = -1;
	memset(s->data, 0, sizeof(double)*MAX_data_size);
}
int is_stack_empty(struct stack *s) {
	if (s->top < 0) return 1;
	return 0;
}
int is_stack_full(struct stack *s) {
	if (s->top >= MAX_data_size-1) return 1;
	return 0;
}
int push(struct stack *s, double data) {
	if (is_stack_full(s)) return -1;
	s->data[++(s->top)] = data;
	return 0;
}
double pop(struct stack *s) {
	if (is_stack_empty(s)) return -1;
	return s->data[(s->top)--];
}
int main() {
    struct queue q;
	struct stack s;

	init_queue(&q);
	init_stack(&s);
}

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

문제

문제

출처

ICPC

시간초과가 나오는 이유를 모르겠습니다 도와주세요ㅠㅠ

siriusbug257 1년 전 0

byeongkeunahn 1년 전 1

steve193 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말