글 읽기 - 답은 맞았는데 이렇게 풀어도되나요?

wggwvs 1년 전 0

2750문제와 동일하게 그냥 제출했는데 정답처리가 되네요... 그냥 동적배열 할당하고 sort함수로 정렬하고 출력했는데 그냥 이렇게 해도 되냐요? 아니면 다른 출제자의 의도가 있는건가요....

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	int a = 0;
	cin >> a;
	int* array = new int[a];
	for (int i = 0; i < a; i++) {
		cin >> array[i];
	}

	sort(array, array + a);
	for (int i = 0; i < a; i++) {
		cout << array[i]<<"\n";
	}
	delete[]array;
}

zenith82114 1년 전 0

두 문제의 차이는 O(N^2) 복잡도를 허용하는지 않는지입니다.

wggwvs 1년 전 0

저는 이중포문을 이용하지 않았기때문에 o(n)이라 괜찮은거죠?

zenith82114 1년 전 0

이 코드가 통과하는 이유는 이중 for문이 없어서가 아니라

sort 함수가 O(NlogN) 복잡도를 가지는 알고리즘

또는 그런 알고리즘들의 혼합된 형태를 사용하기 때문입니다.

비교 기반 정렬은 O(NlogN)보다 빠를 수 없습니다.

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

문제

문제

출처

ICPC

답은 맞았는데 이렇게 풀어도되나요?

wggwvs 1년 전 0

zenith82114 1년 전 0

wggwvs 1년 전 0

zenith82114 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말