kitae135   9달 전

물이 범람하는 시간을 다 계산하고 고슴도치를 진행시키는거보다

물 1회 진행 -> 고슴도치 1회 진행이 더 빠를거라고 생각해서 구현해봤는데

10%도 못가서 시간초과가 뜨네요.. 오래 걸리거나 무한루프에 빠질부분이 있나요..?ㅠㅠ

hello70825   9달 전

pop(0)으로 하면 한 번 실행마다 O(n)이 걸립니다.

O(1)로 뺄 수 있는 deque로 하세요


hello70825   9달 전

https://excelsior-cjh.tistory....

위 링크에서 deque,appendleft,popleft만 기억하시면 됩니다.

kitae135   9달 전

답변 감사합니다! pop(0)이 O(n)이 걸리는줄은 처음알았네요...

deque 로 바꿔서 돌려봤는데 아직 시간초과가 뜹니다


문제 tc를 찾아냈는데 이런 tc에 대응하려면 제 코드 설계부터가 잘못된걸까요?

slikar.in.7

slikar.out.7

hello70825   9달 전

60줄 때문에 무한루프를 돌고 있습니다

60줄을 72줄 if문안에 넣어주면 됩니다.

값을 바로바로 갱신해주지 않으면 무한루프에 빠지게 됩니다.

kitae135   9달 전

헉 감사합니다!! 덕분에 해결되었습니다.

다른 사람이 짜놓은 코드 보는게 저한텐 참 어려운 일로 느껴지곤하는데

정말 귀신같이 가려운 곳을 찾아주시네요ㅠㅠ 진짜진짜 감사드립니다!!!

kitae135   9달 전

혹시 차후에 질문글 보실분들을 위해 남겨둡니다.


pop(0)와 popleft()의 성능차이를 확인해보고 싶어서 pop(0) 로도 채점해보았는데,

이 문제에선 큐 크기가 최대 50이라서 라이브러리 임포트 비용이 더 컸던건지, 오히려 결과가 더 좋게나왔습니다.

하지만 실제로 실험해보니 popleft의 성능이 월등합니다 :)

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