글 읽기 - set 시간복잡도

effort0819 5년 전 0

set으로 문제를 해결 시 시간초과가 나는데 시간 복잡도가 어떻게 될까요?

#include <iostream>
#include <set>

using namespace std;

int main(){
	int N, temp;
	set<int> s;
	scanf("%d", &N);

	while(N--){
		scanf("%d", &temp);
		s.insert(temp);
	}

	for(int x : s){
		printf("%d\n", x);
	}

	return 0;
}

djm03178 5년 전 0

이 코드는 O(nlogn)이지만, 본래 시간이 넉넉한 문제는 아니고 set은 그 중에서도 매우 느린 속도를 자랑합니다. set이 균형 이진 트리를 사용하기 때문인데, 이에 대해 알아보시면 왜 set이 느릴 수밖에 없는지 알 수 있습니다.

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

문제

문제

출처

ICPC

set 시간복잡도

effort0819 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말