dydsj0920   2년 전

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

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

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

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


chogahui05   2년 전

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


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

chogahui05   2년 전

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

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

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


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

Green55   2년 전

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

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

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

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

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


dydsj0920   2년 전

답변들 감사합니다

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