글 읽기 - 10989 시간 초과 관련 질문이 있습니다.

onebellfortune 2년 전 0

안녕하세요, 10989번 시간 초과 관련 문제가 있습니다.

while문으로 하면 정답으로 나오는데

아래 주석 처리된 30~32 line으로 하면 시간이 초과됩니다.

왜 시간 초과가 되는 지 궁금합니다.

#include <iostream>
#include <cstdio>

using namespace std;





int main(){
    int num_of_data;
    int numbers[10001];
    
    int num;

    for(int i=1;i<=10000;i++){
        numbers[i]=0;
    }
    scanf("%d",&num_of_data);
    for(int i=0;i<num_of_data;i++){
        scanf("%d",&num);
        numbers[num]++;
    }

    for(int i=1;i<=10000;i++){
        while(numbers[i]>0){
            printf("%d\n",i);
            numbers[i]--;
        }
        /*for(int j=0;j<numbers[i];j++){
        printf("%d\n",i);
        }*/
    }

    
}

djm03178 2년 전 1

아마 별 차이는 없을 것인데 실행 시마다의 오차로 인한 것 같습니다. while문을 쓴 이 코드 그대로도 내봤는데 저는 시간 초과를 받았습니다.

통과된 코드도 2800ms대로 시간 제한에 가까우니 오차에 의해 얼마든지 결과가 달라질 수 있어 보입니다.

djm03178 2년 전 1

참고로 이 코드를 C99에 맞게 바꿔서 while문으로 두 번 내보았는데, 한 번은 시간 초과가 나고 한 번은 2600ms로 통과됐습니다. 오차가 꽤 큽니다.

TLE: http://boj.kr/8735b3c756db4a00...

AC: http://boj.kr/bed9a12aab9e4831...

onebellfortune 2년 전 0

그렇군요.. 이런 경우에는 그러면 시간 복잡도를 줄여야 하는 것인가요?

djm03178 2년 전 1

시간 복잡도는 더 줄일 방법이 없습니다. 상수 시간을 줄일 수밖에 없습니다.

하지만 제가 백준님께 말씀드려서 시간 제한을 늘렸으니 이제 괜찮습니다.

onebellfortune 2년 전 0

아하..감사합니다

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