문제

https://www.acmicpc.net/problem/1158

문제 설명

• 리스트에서 순서대로 pop하기 때문에, Queue자료형을 써야할 것이라 생각했으나. python에서 제공하는 Queue자료형이 그냥 리스트의 pop연산보다 더 느린 계산 결과를 얻었다.
  
• 코드

# Python에서 기본 제공하는 queue 자료형
import queue

# 정수 2개를 문자열 입력으로 받아, split한 후, int형으로 바꾼다.
order = list(map(int, input().strip().split()))
# queue 선언
que = queue.SimpleQueue()
# queue 초기화
[que.put(i) for i in range(1, order[0]+1)]
answer = []

count = 0

# que의 사이즈를 확인하고, 0이 될 때 까지 반복, 그냥 while que로는 무한루프가 된다.
while que.qsize():
    count += 1
    # que.get()에서 block=False옵션을 넣지 않으면 무한 대기 상대가 된다.
    num = que.get(block=False)

    if not (count % order[1]):
        answer.append(str(num))
    else:
        que.put(num)

print('<',(', ').join(answer), '>', sep='')

• 다른 자료형인 deque를 사용해본다.
• 코드

from collections import deque

order = list(map(int, input().strip().split()))
que = deque(range(1, order[0]+1))
answer = []

count = 0
while que:
    count += 1
    num = que.popleft()

    if not (count % order[1]):
        answer.append(str(num))
    else:
        que.append(num)

print('<',(', ').join(answer), '>', sep='')

• 그러나 역시 느린 결과를 보여준다.

• 마지막으로 리스트 자료형의 pop모듈을 사용해본다.
• 코드

order = list(map(int, input().strip().split()))
que = list(range(1, order[0]+1))
answer = []

index = 0

while que:
    # 인덱스의 문제 간격만큼 떨어진 자리를 answer리스트에 넣는다. 
    # len(que) 나머지연산으로 최대값을 넘지 않도록 한다.
    index = (index+order[1]-1)%len(que)
    answer.append(str(que.pop(index)))

print('<',(', ').join(answer), '>', sep='')

• 이전 queue자료형과 다르게 매우 빠른 결과를 보여주었다.
• queue자료형은 한 데이터당 pop과 append연산을 해야한다. O(N^2)
• list자료형에서 pop연산은 index를 바로 계산하여 pop연산 후, 남은 리스트를 연결하는 작업만 하면 된다. O(M^2), N >= M
• 만약 원소가 항상 앞에서부터 빼야한다면 queue가 빠르지만, 원소가 중간 또는 마지막에 있다면 list.pop()이 더 빠를 것이다.