kangwh0617   7달 전

위 코드는 정답이고 아래 코드는 시간초과네요

두 코드 모두 에라토스테네스의 체를 한번 돌리고 1부터 n까지 순회하며 가장 작은 소인수 배열을 생성하는데 왜 딕셔너리를 이용하였을때 시간초과가 날까요?

제 생각에는 오히려 배열을 선언해서 할 때가 0부터 5000000까지 돌면서 배열을 생성하니 시간이 더 오래 걸릴거라고 생각했는데 아니더라구요

shjohw12   7달 전

딕셔너리가 해싱으로 구현되어있는 것으로 아는데, 시간복잡도는 O(1) 이지만 list보다는 당연히 느립니다

kangwh0617   7달 전

같은 O(1)짜리 탐색이라도 조금 더 느리군요.... 배워갑니다 감사합니다

djm03178   7달 전

코드는 삭제하지 말아주세요. 나중에 질문을 보는 사람에게 도움이 될 수도 있는 자료입니다.

kangwh0617   7달 전

수정했습니다

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