---

백준 2174번 '카드2' 문제와 문제 링크
백준 11866번 '요세푸스 문제 0' 을 풀고 기록을 남긴다. 문제 링크

---

📚 collections

collections 라이브러리는 파이썬에서 자료구조를 제공하는 표준 라이브러리다.
deque 모듈을 통해 스택과 큐를 쉽게 구현할 수 있다.

from collenctions import deque

---

스택

from collections import deque

s = deque()

# 데이터 추가
s.append(1)
s.append(2)
s.append(3)

# 데이터 삭제
print(s.pop()) # 3 
print(s.pop()) # 2
print(s.pop()) # 1

사실, 파이썬에서 스택은 리스트의 기능으로 기본적으로 구현되어 있다.
스택을 사용하기 위해선 그냥 리스트의 append 와 pop 기능을 간단히 사용하자.

---

큐

from collections import deque

q = deque()

# 데이터 추가
q.append(1)
q.append(2)
q.append(3)

# 데이터 삭제
print(q.popleft())  # 1
print(q.popleft())  # 2
print(q.popleft())  # 3

---

rotate()

deque 자료형의 rotate() 함수를 사용해서 리스트를 회전시킬 수 있다.
함수 안에 음수를 입력하면 왼쪽으로 회전한다.

from collections import deque

test = [1,2,3,4,5]
q = deque(test)
q.rotate(-1)

print(list(q))

--> [2,3,4,5,1]

함수 안에 양수를 입력하면 오른쪽으로 회전한다.

from collections import deque

test = [1,2,3,4,5]
q = deque(test)
q.rotate(2)

print(list(q))

--> [4,5,1,2,3]

---

문제풀이 예시

아래는 백준 2174번 '카드2' 문제의 정답 코드이다. 문제 링크

from collections import deque

n = int(input())
q = deque()

for i in range(n):
    q.append(i+1)

while(len(q) != 1):
    q.popleft()
    q.append(q.popleft())

print(q[0])

아래는 queue 모듈을 사용한 풀이로, 위와 같은 알고리즘이지만
라이브러리 내 시간복잡도가 커 시간초과가 발생한다. (사용 자제)

import queue

n = int(input())
q = queue.Queue()

for i in range(n):
	q.put(i+1)

while(q.qsize() != 1):
    q.get()
    q.put(q.get())

print(q.get())

---

문제풀이 예시

아래는 rotate() 함수를 이용해 쉽게 풀 수 있는
백준 11866번 '요세푸스 문제 0'의 정답 코드이다. 문제 링크

from collections import deque
import sys
input = sys.stdin.readline

n, k = map(int,input().split())
q = deque(i for i in range(1, n+1))

print('<', end="")
while(len(q) != 1):
    q.rotate(-(k-1))
    print(q.popleft(), end=", ")

print(q[0], end="")
print('>')