글 읽기 - multiset 시간초과 질문드립니다.

dydsj0920 6년 전 0

multiset을 사용하면 시간초과가 나네요

혹시나 set으로 바꿔도 시간초과가 나구요.

set, multi_set이 그렇게 느린 STL인가요?

equal_range나 lower,upper_bound로는 해결되던데요

int main() {
	int n, m;
	scanf_s("%d", &n);

	set<int> a;
	for (int i = 0; i < n; i++) {
		int x;
		scanf_s("%d", &x);
		a.insert(x);
	}

	scanf_s("%d", &m);
	for (int i = 0; i < m; i++) {
		int num;
		scanf_s("%d", &num);
		printf("%d ", a.count(num));
	}
	printf("\n");

	return 0;
}

chogahui05 6년 전 1

http://www.cplusplus.com/refer...

Time Complexity = Logarithmic in size and linear in the number of matches.

chogahui05 6년 전 1

set 자체가 그렇게 느린 자료구조는 아닙니다. 만..

rb 트리로 구현되어 있어서 더 많은 메모리를 소모할 겁니다. 예를 들어서.

얼마나 편향되어 있는지.. 자식 둘이 어떻게 연결되어 있는지. 등등..

시간도 약간 더 걸릴 거고요..

Green55 6년 전 3

일단, 제출하신 코드는 예제도 제대로 출력하지 못합니다.

set은 단순히 원소가 있는지/없는지만 저장하기 때문에, 개수를 출력해야 하는 이 문제에서 적합하지 않습니다.

multiset 언급을 하신거 보시면 원소를 전부 멀티셋에 넣고 카운팅 하시는 방법을 쓰신거 같은데, 이러면 시간 초과가 날겁니다.

따라서 키값만 저장하는 set이 아닌, 추가로 키와 함께 값도 하나 저장 할 수 있는 map을 쓰시면 문제를 해결 하실 수 있습니다.

이 문제에서는 정렬하여 저장할 필요가 없기때문에, c++11부터 사용 가능한 unordered_map을 사용하시면 더 빠른시간에 해결 가능합니다.

dydsj0920 6년 전 0

답변들 감사합니다

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

문제

문제

출처

ICPC

multiset 시간초과 질문드립니다.

dydsj0920 6년 전 0

chogahui05 6년 전 1

chogahui05 6년 전 1

Green55 6년 전 3

dydsj0920 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말