글 읽기 - 무한루프 vs 팩토리얼 시간차이

wjddydgns99 4년 전 1

맨 처음에 제 코드에서 for (int i = 0;; i++)

부분이, for (int i = 0;i<Factorial(num); i++)이었습니다. 근데 어째서 이게 시간초과고 무한루프가 통과하는 걸까요?전 시간복잡도는 똑같다고 생각했습니다.

#include<iostream>
using namespace std;
void Swap(int*x, int*y)
{
   int tempt = *x;
   *x = *y;
   *y = tempt;
}
int Factorial(int a)
{
   if (a == 1) return 1;
   else
   {
      return a * Factorial(a - 1);
   }
}


int main()
{
   int num;
   cin >> num;
   int *p = new int[num];
   for (int i = 0; i < num; i++) p[i] = i + 1;
   for (int i = 0; i < num; i++) cout << p[i]<<" ";
   cout << "\n";
   for (int i = 0;; i++) {
      int x = num - 1;
      while (x >= 0 && p[x] <= p[x - 1])x--;
      if (x <= 0)
      {
         return 0;
      }
      int y;
      for (y = num - 1; y >= 0; y--)
      {
         if (p[x - 1] < p[y])
         {
            Swap(&p[x - 1], &p[y]);
            break;
         }
      }
      y = num - 1;
      while (x < y)
      {
         Swap(&p[x], &p[y]);
         x++; y--;
      }

      for (int i = 0; i < num; i++) cout << p[i]<<" ";
      cout << "\n";
   }
   return 0;

}

djm03178 4년 전 2

아니요, 이 코드에서 27번째 줄만 바꾸면 시간 초과가 안 납니다.

질문을 올릴 때는 반드시 틀린 코드를 한 글자도 다름없이, 그대로 복붙해서 올려주세요. 맞는 코드를 올려봐야 아무것도 봐드릴 게 없습니다.

지금처럼 맞는 코드를 올려놓고 틀린 코드와 다른 점을 말로 설명하면 꼭 실제로 제출한 것과 다른 부분이 생깁니다. 바로 51번째 줄입니다. 시간 초과가 난 코드에서는 "\n"이 아닌 endl이 쓰여 있습니다. 이 때문에 시간 초과가 나는 것이고, factorial(num)을 반복문에 쓴 것은 거의 아무런 영향이 없습니다.

wjddydgns99 4년 전 0

감사합니다. 덕분에 해결했습니다.

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

문제

문제

출처

ICPC

무한루프 vs 팩토리얼 시간차이

wjddydgns99 4년 전 1

djm03178 4년 전 2

wjddydgns99 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말