gudgns1995   2년 전

문제없이는 잘 도는데 시간초과로 뜨네요 ㅠㅠ 무엇이 문제일까요 ㅠㅠ 도와주세요..

dnwlscjf167   2년 전

8, 12 번째 줄에 있는 arr.pop(0) 연산은 좋지 않습니다. 시간 복잡도가 O(n)나오는 것으로 알고 있습니다. 

https://www.acmicpc.net/blog/v...

쓰실려면 collections.deque 사용하셔야 O(1)에 연산 가능할 것 같습니다.

그리고 연산 자체도 시간이 많이 걸리는 것 같습니다. 

만약 5000 5000 입력이 들어오게 되면 5000 * 5000번 pop하고 append하는 연산을 계속 반복하게 되서 시간이 많이 걸릴 수 밖에 없을 것입니다.

다른 방법을 한 번 생각해보시면 좋을 것 같습니다.

저도 아직 공부중이라 확실하게 이거다라고 확정드리진 못하겠지만, 제 생각에는 이런 점들이 시간 초과의 원인들인 것 같습니다. :)

canoc   2년 전

일단 저는 pop()을 쓰지 않고 값이 들어있는 곳의 시작 위치는 begin, 끝나는 곳의 바로 다음 위치를 end가 가리키게 해서 pop()은 사용하지 않았습니다.

그리고 pypy3으로 돌려보니 코드를 전혀 수정하지 않고도 맞았다고 뜨더군요.. 위에 댓글 달아주신 분이 알려주신 링크 들어가보니 python으로 시간초과가 

뜨면 pypy로 돌려보라고 나와있습니다.

혹시나 저처럼 파이썬으로 코드를 짰다가 시간 초과가 뜨신 다른 분들이 이 글을 보실까 싶어 댓글 남겨봅니다.. 기초적인 내용이지만 도움 되었길 바라요

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