2812번 - 크게 만들기
안녕하세요
2812번 크게 만들기 문제 질문입니다.
python 코드이고 Pypy로 제출해도 시간 초과가 뜨네요
어떤 부분에서 시간을 많이 잡아먹는지 굼금합니다
최대 k개의 지울 부분을 찾기 위해 매번 최대 O(n)번을 움직였다가 시작으로 돌아가기를 반복하고 있으므로 O(kn)의 시간이 걸립니다.
원소를 하나씩 지울 때마다 파이썬의 리스트는 그 지워진 원소 뒤의 원소들의 인덱스를
모두 수정해야 합니다. 여기에서도 많은 시간이 소모됩니다.
deque 자료구조를 사용하시면 시간 소모를 줄일 수 있습니다.
첨부한 코드를 실행시켜보면 동일한 동작을 하지만 시간 차이가 매우 크다는 것을 알 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
lesk012 2년 전
안녕하세요
2812번 크게 만들기 문제 질문입니다.
python 코드이고 Pypy로 제출해도 시간 초과가 뜨네요
어떤 부분에서 시간을 많이 잡아먹는지 굼금합니다