글 읽기 - 실행 시간을 어떻게 줄여야 할까요?

hoseong8115 1년 전 0

qsort함수도 써보고 했는데 계속 시간 초과가 뜹니다...

#include "stdio.h"
#include "stdlib.h"

int compare(const void *a, const void *b) {
    int num1 = *(int *) a;
    int num2 = *(int *) b;
    if (num1 < num2)
        return -1;
    if (num1 > num2)
        return 1;
    return 0;
}

int main() {
    int N;
    scanf("%d", &N);
    int arr[N], alr[N];
    for (int i = 0; i < N; ++i) {
        int a;
        scanf("%d", &arr[i]);
    }
    qsort(arr, sizeof(arr) / sizeof(int), sizeof(int), compare);
    for (int i = 0; i < N; ++i) {
        int sig = 0;
        for (int j = 0; j < i; ++j) {
            if (alr[j] == arr[i]) sig = 1;
        }
        if (sig == 0) {
            printf("%d\n", arr[i]);
            alr[i] = arr[i];
        }
    }
}

beawall 1년 전 0

퀵소트는 최악의 경우 O(n^2)으로 알고 있는데 c++의 sort 함수같이 O(nlogn)을 보장하는 함수를 설계하거나 사용해보세요

hoseong8115 1년 전 0

알겠습니다.

한번 해보겠습니다

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

문제

문제

출처

ICPC

실행 시간을 어떻게 줄여야 할까요?

hoseong8115 1년 전 0

beawall 1년 전 0

hoseong8115 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말