글 읽기 - 시간 초과...

kbj2288 3년 전 0

code blocks 에서는 돌아가는데

백준에서는 시간초과가 나오네요

뭐가 문제일까요....

#include <iostream>
using namespace std;

int main()
{

    int* Array;
    int num;

    cin >> num;

    Array = new int[num];

    for(int i=0; i<num; i++)
    cin >> Array[i];

    for(int j=0; j<num; j++)
    {
        for(int k=j; k<num; k++)
        {
        if(Array[j] > Array[k])
           {
               int temp;
               temp = Array[k];
               Array[k] = Array[j];
               Array[j] = temp;
            }
        }
    }

    cout << Array[0] << " "<< Array[num-1]<<"\n";

    delete [] Array;
    return 0;
}

BaaaaaaaaaaarkingDog 3년 전 0

지금 코드는 버블 정렬을 수행한 후 제일 앞의 원소와 뒤의 원소를 출력하는 코드인데 버블정렬(17 to 29 line)의 시간복잡도가 O(N^2)이기 때문에 N이 최대 백만인 이 문제에서는 당연히 시간초과가 발생하게 됩니다.

kbj2288 3년 전 0

그럼 저 정렬 부분을 다르게 바꿔야한다는 말씀이신거죠?

leinad2 3년 전 0

굳이 정렬을 해야될까요? 잘~ 생각해보세요

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

문제

문제

출처

ICPC

시간 초과...

kbj2288 3년 전 0

BaaaaaaaaaaarkingDog 3년 전 0

kbj2288 3년 전 0

leinad2 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말