[질문] 이거 진짜 시간초과 왜뜨는거야??

[익명(23.251)]

백준 1918번 문제인데위쪽 코드는 시간초과, 아래건 통과야

다른건 다 똑같고 getPriority함수랑
마지막 else문 안에서 priority비교하는것만 달라

도대체 무슨차이때문에 시간초과가 뜨는거야?



#include <stdio.h>
#include <stdlib.h>
#define MAX 200

int getPriority(char c)
{
    if (c == '+' || c == '-')
        return 1;
    if (c == '*' || c == '/')
        return 0;
    return -1;
}

int isOperator(char c)
{
    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')')
        return 1;
    else
        return 0;
}

void infixToPostfix(char *str)
{
    char stk[MAX] = {0};
    int top = 0;

    for (int i = 0; str[i]; i++)
    {
        char c = str[i];
        if (!isOperator(c))
            printf("%c", c);
        else if (c == '(')
            stk[++top] = c;
        else if (c == ')')
        {
            while (stk[top] != '(')
                if (top)
                    printf("%c", stk[top--]);
            if (top)
                top--;
        }
        else
        {
            while (top && getPriority(c) >= getPriority(stk[top]))
                printf("%c", stk[top--]);
            stk[++top] = c;
        }
    }

    while (top)
    {
        printf("%c", stk[top--]);
    }
}

int main()
{
    char infix[MAX];
    scanf("%s", infix);

    infixToPostfix(infix);

    return 0;
}



#include <stdio.h>
#include <stdlib.h>
#define MAX 200

int getPriority(char c)
{
    if (c == '+' || c == '-')
        return 0;
    if (c == '*' || c == '/')
        return 1;
    return -1;
}

int isOperator(char c)
{
    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')')
        return 1;
    else
        return 0;
}

void infixToPostfix(char *str)
{
    char stk[MAX] = {0};
    int top = 0;

    for (int i = 0; str[i]; i++)
    {
        char c = str[i];
        if (!isOperator(c))
            printf("%c", c);
        else if (c == '(')
            stk[++top] = c;
        else if (c == ')')
        {
            while (stk[top] != '(')
                if (top)
                    printf("%c", stk[top--]);
            if (top)
                top--;
        }
        else
        {
            while (top && getPriority(c) <= getPriority(stk[top]))
                printf("%c", stk[top--]);
            stk[++top] = c;
        }
    }

    while (top)
    {
        printf("%c", stk[top--]);
    }
}

int main()
{
    char infix[MAX];
    scanf("%s", infix);

    infixToPostfix(infix);

    return 0;
}

https://www.acmicpc.net/problem/1918

[익명(218.39)]

ps 갤가면 고수들이 잘 답변해줌

[토끼주문(icyselec)]

위쪽 코드는 당장 예제 입력 1만해도 무한 루프걸려. 딱봐도 조건 검사 때문에 무한 루프라 어제 말할려고 했는데 확실하진 않아서 직접 돌려볼 시간이 없기도 했고 최소한 예제 입력 정도는 테스트했을거라 생각했는데 아닌가보네. 근데 알고 싶은건 어떻게해서 시간 초과(무한 루프)가 뜨는지 알고 싶다는 건가?

[토끼주문(icyselec)]

infixToPostfix 함수의 두번째 else if에서 짝이 맞는 괄호를 찾는 과정에서 무한 루프가 발생할 수 있음. 너가 말한 우선순위 비교하는 부분에서 여는 괄호가 저장된 부분을 다른 연산자가 잡아먹어서 조건이 안맞게되고 무한 루프가 걸리는듯.