글 읽기 - (C) 시간 초과 질문

dragonmaster12 3년 전 0

먼저 n으로 배열의 크기를 입력받고.. 그 다음에 동적 메모리 할당으로 배열의 크기를 정해준 다음에

버블 정렬을 해서 arr[0]값과 arr[n-1]값이 각각 최소, 최댓값이 되게끔 설정해놓았는데..

Visual Studio에서 정상적으로 빠르게 컴파일 되는데 제출하니깐 시간 초과라고 뜹니다. 혹시 어떤게 문제인 지 봐주실수 있을까요?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;

    scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    int min, max, index;

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &index);
        arr[i] = index;
    }

    for (int i = n- 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
      
        }
    }
    
    min = arr[0], max = arr[n - 1];

    printf("%d %d", min, max);
    
    free(arr);
    return 0;
}

jerrome2685 3년 전 0

이 문제를 버블 정렬 하시면 O(n^2)으로 TO가 됩니다. 어차피 최대와 최소만 구하면 되므로, O(N)으로 갱신 하던지 O(nlogn)으로 STL sort를 하셔야 합니다.

dragonmaster12 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

(C) 시간 초과 질문

dragonmaster12 3년 전 0

jerrome2685 3년 전 0

dragonmaster12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말