whdgurclzls   3년 전

안녕하세요!

트라이 딕셔너리를 이용해서 구현했다가 시간초과가 나서 리스트로 다시 짜봤습니다.

그런데 리스트로 짠거 마저 시간초과가 나네요.. 

제가 트라이 개념을 잘못 이해한 부분이 있는건가요??  그렇지 않다면 어떻게 해야 시간을 더 줄일 수 있을까요??

shg9411   3년 전

현재 코드의 경우 n번의 입력을 받다가 일관성이 없을 때 입력을 그만 받기 때문입니다.

리스트보다는 딕셔너리가 효율적이고요

whdgurclzls   3년 전

아!!  어떻게든 시간 단축시키려다가 그부분은 생각도 못하고 있었네요..


근데 왜 리스트보다 딕셔너리가 효율적일까요? 

공간적으로는 이해가 가도 시간적으로는 최악의 경우를 따졌을 경우 딕셔너리가 O(n)이고 리스트가 O(1)이라 생각되는데.. 두 코드 돌려봐도 사전이 더 빠르네요..? 리스트 선언하는거때문에 그런건가..

암튼 덕분에 잘 해결했습니다 감사합니다!!

좋은 하루 되세요 :)

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