백준 1158, 백준 11866 - 요세푸스 문제

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

1158번: 요세푸스 문제

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

11866번: 요세푸스 문제 0

문제 설명이 아예 똑같은 문제다. 다만 1158번이 조금 더 초기 K,N에 대한 입력값의 최대치 상한이 높다.

 

이 문제는 큐(Queue)로 푸는 문제다. 보통 큐를 구현하라고 하면 Python에서는 list로 구현하는 게 일반적인데, list는 구조적으로 다른 언어(Java, C 등)의 array와 같은 개념이다. 문제는 이런 array는 무작위 접근에 최적화된 자료구조이기 때문에 pop(0)이나 insert(0, x)는 성능적으로 매우 불리하다. 이렇게 되면 시간복잡도가 O(N)이 되어서 데이터가 많이 들어있을수록 해당 명령을 수행하는 데 시간이 오래 걸리기 때문이다. 이를테면, pop(0)으로 첫 값을 제거하게 되면 그 뒤에 있는 모든 데이터를 다 한 칸씩 차례차례로 당겨줘야 하고, insert로 맨 앞에 데이터를 삽입하게 되면 그 전에 모든 데이터를 뒤로 한 칸씩 다 밀어줘야 하기 때문에 시간이 너무 오래 걸린다.

 

Python에서는 보다 효과적인 Queue 구현을 위해, collections라는 모듈에서 deque(Double-Ended-QUEue, DEQUE)라는 자료구조를 지원해준다. Double-Ended라는 말에서 볼 수 있듯 이 자료구조는 데이터를 앞에서도 넣을 수 있고(Queue), 데이터를 뒤에서도 넣을 수 있다(Stack).

 

deque는 list의 메소드에 존재하지 않는 popleft()를 제공해 준다. 이는 첫 번째 데이터를 제거할 수 있게 된다. 시간 복잡도는 O(1)이다.

 

deque의 appendleft(x)를 사용하면, 데이터를 맨 앞에 삽입할 수 있게 된다. 시간 복잡도는 O(1)이다.

 

대신 deque도 i번째 데이터에 접근하기 위해서는 맨 앞/뒤부터 순차적으로 접근해야 하므로 이는 O(N)의 시간복잡도를 갖는다.

 

참고 : https://www.daleseo.com/python-queue/

파이썬에서 큐(queue) 자료 구조 사용하기

 

from collections import deque

n,k = map(int, input().split())
arr = deque([i for i in range(1,n+1)])
out_arr = []
while len(arr)>0:
    for i in range(k):
        if i<k-1:
            arr.append(arr.popleft())
        else:
            out_arr.append(arr.popleft())
print("<", end='')
for num in out_arr:
    if num!=out_arr[-1]:
        print(f'{num},',end=' ')
    else:
        print(f'{num}',end='')
print(">")

문제로 돌아와서, n,k 값을 입력받고, 배열을 deque로 생성한 뒤 deque 내에는 1부터 n까지의 숫자를 집어넣는다. 그리고 제거되는 순서대로 값을 집어넣을 out_arr을 만든다.

 

deque 내에 모든 요소가 없어질 때까지, 매 번 요세푸스에서 K번째 사람이 되기 전까지는 맨 앞의 요소를 맨 뒤로 보내줘야 한다. 그러므로 arr.popleft()한 값을 그대로 다시 arr.append()로 뒤로 보내준다. 만일 K번째 사람이라면, popleft한 것을 out_arr로 보내준다.

 

이후 문제에서 요구하는 출력 양식에 맞게 출력해준다.(개인적으로 이 쪽이 조금 더 구현하기 귀찮았다.)