[백준/Python] - 11866번 요세푸스 순열

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

 

제출코드

import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().strip().split())
N_list = deque([i for i in range(1,N+1)])
ans_list = []

while N_list:
    for _ in range(K-1):
        N_list.append(N_list.popleft())
    ans_list.append(N_list.popleft())
print("<", end = "")
for i in range(N):
    if i == N-1:
        print(ans_list[i], end = ">")
    else:
        print(ans_list[i], end = ", ")

맨 처음에 로직을 짤 때는 그냥 list에 append 하고 숫자가 기준값을 넘으면 나머지 연산을 하여 나눠주는 방식으로 했다. 하지만 너무 복잡해지고 예제 출력값도 안나와서 그냥 구글링 해서 풀었다...

 

여기서 알아낸 점이 deque였다.

---

deque란?

deque는 양쪽에서 값을 넣고 뺄 수 있는 스택과 큐의 기능이 둘 다 가능한 파이썬 객체이다. 이걸 줄여서 덱이라고한다.

큐처럼 사용 가능하고, 스택처럼도 사용이 가능하다.  

from collections import deque

dq= deque('soccer')
print(dq)

deque출력

1.스택 구현:  append, pop

스택은 LIFO(Last In First Out)로 마지막에 들어온 값이 나온다.

from collections import deque

dq= deque('soccer')
print(dq)

dq.append('love')
print(dq)
dq.pop()
print(dq)

 

2.큐 구현: popleft() appendleft()

큐는 FIFO로 왼쪽에서 들어오고 오른쪽에서 나간다.

from collections import deque

dq= deque('soccer')
print(dq)

dq.appendleft('love')
dq.pop()
print(dq)

 

3. 덱 구현

덱은 double ended enque를 줄여서 말한 것으로 deque이다. 양방향으로 값을 넣고 뺄 수 있다.

덱은 front에서 추가 삭제가 이뤄지는 것은 물론 rear에서도 추가 삭제가 이루어져 양방향

양방향 연결리스트로 덱을 구현하는 경우가 많다.

덱의 구성 핵심함수는

• 앞으로 넣기(appendleft())
• 뒤로 넣기(append())
• 앞으로 빼기(popleft())
• 뒤로 빼기(pop())

이렇게 구성되어 있다.