pop(0) 연산이 이유는 잘 모르겠으나 시간이 많이 걸립니다.

연산별 속도 비교를 해드릴게요.(각 연산별 1~100,000으로 채워진 리스트를 빌 때까지, 1개씩 제거)

   1. pop() : 0.008043050765991211초

   2. pop(0) : 1.1850876808166504초

   3. deque의 popleft() : 0.006011009216308594초

(deque를 모르실까봐 알려드리면, 큐(queue)를 구현할 때, 주로 사용하는 모듈로 좌측부터 제거하거나, 추가하는 명령어가 있고, 이를 빠르게 실시해줍니다,)

보시면 한눈에 봐도 pop(0) 연산이 느린 것을 확인하실 수 있습니다. 

코드 작성하시것을 보시면 일단 pop(0)연산을 하고 res나 다시 queue에 append합니다.

그럼 pop(0)연산이 n*(k-1)정도 수행될 것입니다. 따라서 pop(0)연산하는 부분을 수정해야할 거 같습니다.

매번 pop(0)을 하는 것보다, 뽑아내야 할 위치(target)를 찾은 다음에 pop(target)를 한번만 해주는 방식으로 해보세요.

말씀하신 대로 pop(0)이 시간이 많이 걸리는 것 같아서 deque로 바꿨더니 통과가 되네요! 

그런데 말씀하신 방법으로는 어떻게 바꿔야할지는 잘 모르겠네요...

아무튼 감사드립니다...!!

저는 현재 위치(제거된 후의 인덱스)에 k를 더하고 그게 남아있는 원소의 수보다 크면 나머지를 구해서 pop해줬습니다.

파이썬의 리스트는 연속된 데이터를 저장하는 값이잖아요? 이게 내부적으로는, 컴퓨터 메모리에 그 데이터가 순서대로 저장되어 있고, 리스트는 그 시작점과 크기만 저장하고 있습니다.

여기서, 리스트에 pop(0)를 수행하면, 그 데이터 맨 앞의 값을 제거한 후 그 뒤에 오는 값을 일일이 전부 한 칸씩 앞으로 당깁니다. 메모리를 옮기는 것도 연산이기 때문에 리스트가 길어질수록 pop(0)에서 소요되는 시간이 길어집니다. 리스트의 맨 앞에 값을 추가하는 것도 비슷한 이유로 매우 느립니다. 반면에 마지막 값만 제거하는 pop()은 그저 리스트의 "데이터 길이"만 줄이면 되기 때문에 매우 빠르게 실행됩니다.

즉, list의 pop(0)가 느린 이유는, 맨 앞의 데이터를 제거하기만 하면 되는 게 아니라, 나머지 값을 다 한칸씩 당겨오기까지 해야 해서 그렇습니다.

반면 deque는 덱 자료형을 구현한 것으로, 맨 앞의 값을 제거하거나 맨 앞에 값을 추가하는 것을 효율적으로 수행할 수 있도록 따로 구현한 자료형입니다. 덱은 리스트와 구현 방식이 다르기 때문에 popleft()가 매우 빠릅니다. 그래서 리스트에서 원소의 맨 앞과 맨 뒤 모두에서 값을 추가하거나 제거할 일이 있으면 리스트 대신 덱을 쓰는 게 좋습니다.