백준 1158 요세푸스 문제 - 큐

1158번: 요세푸스 문제 (acmicpc.net)

1158번: 요세푸스 문제

 

from collections import deque

N, K = map(int, input().split())
lst = [i for i in range(N, 0, -1)]
deq = deque(lst)
lst2 = []
while len(deq) > 0:
    for i in range(K - 1):
        deq.appendleft(deq.pop())
    lst2.append(str(deq.pop()))
print('<'+', '.join(lst2)+'>')

 1 2 3 4 5 6 7 이 동그랗게 앉아있을 때 K가 3이면 +3씩 깡충 뛰기 해서 3 6 2 7 5 1 4 이런식으로 구하는것..

뭔가 큐라는 것을 생각 못했을 때에는.. 어떻게 지나간 자리를 지나갔다고 나타내지? 어렵게 느껴졌었는데

'큐'라는 힌트를 보고 나니까 K - 1만큼 뒤로 보내고 앞으로 온 수를 pop하면서 전체 큐가 빌 때까지 같은 동작을 반복하면 됐었다...

 

로직은 완성됐는데 시간초과가 나서 왜그런지 생각을 해보니

pop(0)을 하면 처음부터 모든 인덱스를 탐색해야 하므로 시간복잡도가 높을 것이라 예상되었다.

그래서 1234567이었던 배열을 7654321로 바꾸고 append -> appendleft / pop(0) -> pop으로 바꾸니 시간초과가 해결되었따.

이때 appendleft를 쓰기 위해 deque를 가져와서 썼다.