pty115   7년 전

입력값이 유일한 정수라서 해쉬셋을 사용했어요

삽입, 탐색 연산이 O(1)인데??? 시간초과네요

배열을 사용해서 다시 구현했는데... 그래도 시간초과...

혹시 입출력에서 시간이 많이 걸리나 싶어서

스캐너 클래스를 새로 구현한 코드를 구해다 사용했어요.

그래도 시간초과 ㅜㅜㅜ


이제 이진탐색트리로도 풀어보려고 하는데

그러면 오히려 해쉬셋보다 시간복잡도가 더 높아지지 않나요?

haja   7년 전

해쉬셋이 어떻게 구현돼 있는지는 잘 모르겠지만, 해쉬셋이 항상 O(1)을 보장하진 않아요. 구현에 따라서 최악에 더 느릴 수도 있어요(어쩌면 O(N)). 반면에 이진탐색트리는 O(lgN)이 보장 돼요

pty115   7년 전

자바 네이티브 해쉬셋을 그대로 사용했어요 ㅜㅜ 이진탐색트리도 시도해봐야겠어요

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