lesk012   2년 전

안녕하세요

2812번 크게 만들기 문제 질문입니다.

python 코드이고 Pypy로 제출해도 시간 초과가 뜨네요

어떤 부분에서 시간을 많이 잡아먹는지 굼금합니다

djm03178   2년 전

최대 k개의 지울 부분을 찾기 위해 매번 최대 O(n)번을 움직였다가 시작으로 돌아가기를 반복하고 있으므로 O(kn)의 시간이 걸립니다.

momiens   2년 전

원소를 하나씩 지울 때마다 파이썬의 리스트는 그 지워진 원소 뒤의 원소들의 인덱스를

모두 수정해야 합니다. 여기에서도 많은 시간이 소모됩니다.

deque 자료구조를 사용하시면 시간 소모를 줄일 수 있습니다.

첨부한 코드를 실행시켜보면 동일한 동작을 하지만 시간 차이가 매우 크다는 것을 알 수 있습니다.

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