시간복잡도와는 아무 상관이 없습니다. 라이브러리를 import하는데에는 상수 시간이 걸리기 때문입니다. 또한, 연산의 수가 많아질수록 deque가 이득이 될 것 같습니다. 이 문제의 경우에는 연산량이 적어서 그런 것 같습니다. (그리고, python에서 20ms는 별로 큰 차이는 아닙니다.)
16928번 - 뱀과 사다리 게임
시간복잡도와는 아무 상관이 없습니다. 라이브러리를 import하는데에는 상수 시간이 걸리기 때문입니다. 또한, 연산의 수가 많아질수록 deque가 이득이 될 것 같습니다. 이 문제의 경우에는 연산량이 적어서 그런 것 같습니다. (그리고, python에서 20ms는 별로 큰 차이는 아닙니다.)
댓글을 작성하려면 로그인해야 합니다.
nicolao00 2년 전
문제를 풀면서 실행시간이 짧은 코드들을 살펴보고있었는데 저는 bfs에서 queue에 값을 넣을 때 첫번째 원소를 pop하는데 시간 복잡도가 O(1)이 소요되는 deque를 사용해왔습니다. 그런데 제 코드보다 시간복잡도가 짧은 코드들이 로직은 비슷한데 deque를 import하지 않고 list.pop(0)로 첫번째 원소를 삭제하는 로직을 사용하고 있었습니다. 제가 알기로 list에서 저런식으로 pop을 하게되면 시간복잡도가 더 증가하는 것으로 알고 있는데 왜 더 빠르지 이것저것 시도해보다가 아래 코드처럼 list.pop(0)을 했지만 단지 from collections import deque를 import 했다는 것 만으로 저 한줄을 지우고 실행시킨 것에 비해 20ms나 더 걸렸습니다.
그래서 제가 내린 결론은 라이브러리를 import 하는데 시간복잡도가 많이 든다는 것인데 그럼 자료구조 측면에서 deque popleft하는 것이 이득인데도 불구하고 라이브러리를 불러오는 추가 시간때문에 list.pop(0)을 쓰는 것이 더 효율적이라고 생각하고 앞으로 문제를 풀면 되는 건가요....? 이것도 상식적으로 이해가 안되긴 한데.. ㅠㅠ