kdhsong   7년 전

set이 속도가많이느린가요 ?

같은알고리즘으로 배열로짯을때는 통과가되는데

string에 스코어를 저장하고 set에 박으니까 시간이 오래걸리네요 ..

소스처럼 string을 set에 저장시키면서 하는건 많이느린가요 ?

set을 쓴이유는 나중에 입력배열에 대해 좀 더 빨리 검색하려고 썼습니다..ㅠ

yclock   7년 전

길이 L짜리 string 2개의 대소비교는 시간복잡도가 O(L)입니다.

따라서 N개의 길이 L짜리 string을 정렬하기 위해서는 O(NL log N)만큼의 시간이 듭니다.

제가 알기로는 아마 string이 vector로 구현되어 있을 겁니다.

vector도 느리고 set도 느리니 더블킬(?!) 아닐까요..?

isac322   7년 전

알고리즘은 모르겠지만 단순히 빠른 검색과 중복 삭제를 원하신다면 unordered_set을 써보세요. http://www.cplusplus.com/reference/unordered_set/u...

Stl에서 그냥 set은 내부적으로 rb트리같은걸 쓴다고 알고있어서 O(logN)이지만 unoredered_set은 해싱을 써서 O(1)인걸로 알고있습니다

kdhsong   7년 전

@yclock @isac322 님 감사합니다! 공부해보겟슴돵ㅎ

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