글 읽기 - 코드를 좀더 단순화하고 싶습니다

hyunsk77 2년 전 0

답은 맞았는데 문제를 해결하는 과정에서 입력받은 수열을 변형하는 과정에서 필요한 알고리즘 수행 횟수(2*n*n)가 너무 많은듯 싶어서 줄이는 방법을 생각해보았으나 따로 떠오르는 방법이 없어서 질문올립니다. 시간초과가 나지 않았다는것은 이정도 수행횟수정도는 n이 충분히 큰 수더라도 괜찮다는 의미인가요?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int n;
    int* arr;
    int* p;
    int index = 1;
    int min = 10000;

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

    for (int i = 0; i < n; i++)
    {
        for (int i = 0; i < n; i++)
        {
            if ((p[i] == 0) && arr[i] <= min)
            {
                min = arr[i];
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == min)
            {
                p[i] = index++;
            }
        }
        min = 10000;
    }
    for (int i = 0; i < n; i++)
    {
        printf("%d ", p[i] - 1);
    }
}

adfsfsf 2년 전 1

정렬을 2번 하는 게 맞긴 합니다. 다만, 정렬 함수 중에는 시간복잡도 O(logN)인 함수가 많으니 그것들을 이용하시면 되겠죠. 아니면, C언어는 <stdlib.h>의 내장함수인 qsort()를 이용하시면 됩니다.

becl3ver 2년 전 1

이 문제에서 N은 50정도입니다. 이 문제의 시간 제한은 2초인데 대략 1초에 1억번 연산이 가능하다고 보시면 됩니다.

lcr7324 2년 전 1

N의 최댓값이 50이니, O(n^2) 알고리즘도 문제 없이 돌아갑니다. N의 최댓값이 수십만을 넘어갔다면 시간 초과를 우려할 수 있는 상황입니다. 하지만 그런 입력은 이 문제에서는 주어지지 않으니 고려하지 않으셔도 됩니다.

hyunsk77 2년 전 0

답변 감사합니다

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

문제

문제

출처

ICPC

코드를 좀더 단순화하고 싶습니다

hyunsk77 2년 전 0

adfsfsf 2년 전 1

becl3ver 2년 전 1

lcr7324 2년 전 1

hyunsk77 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말