[파이썬] 단계별 백준 문제 풀기 - 2164 큐 (카드2)

문제링크

2164번: 카드2

 

 

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

 

---

<<소스코드>>

from collections import deque #deque 모듈 활용
N = int(input()) #첫째줄에 주어지는 카드의 수

#deque 생성, 1~N까지 추가
queue = deque(range(1,N+1))

#queue에 마지막 숫자가 남을때까지 while문 반복
# 제일 왼쪽에 있는 숫자 빼주고, 그 숫자를 앞으로 1번 회전해서 맨 뒤로 가게 함
while len(queue) > 1:
    queue.popleft()
    queue.rotate(-1)

#queue에 마지막에 남는 숫자를 빼서 출력
x = queue.popleft()
print(x)

 

<<결과값>>

6

4

---

deque를 이용하면 쉽게 풀 수 있다.

난 while문에서 하나를 빼주고, 제일 위에있는 숫자를 왼쪽으로 한번 돌려 제일 뒤로 보내줬는데, 생각해보니 queue.append(queue.popleft())로 방금 빼준 숫자를 오른쪽(마지막)에 추가해주면 된다.

while len(queue) > 1:
    queue.popleft()
    queue.append(queue.popleft())

deque는 double-ended queue의 줄임말로, 앞과 뒤에서 데이터를 처리할 수 있는 queue형 자료구조이다. 

 

[deque method]

 - append(x) : deque의 맨 오른쪽(마지막)에 추가

 - appendleft(x) : deque의 맨 왼쪽(앞)에 추가

 - pop() : 맨 오른쪽(마지막)에서 제거, 반환

 - popleft() : 맨 왼쪽(앞쪽)에서 제거, 반환

 - rotate() : 양수는 오른쪽, 음수는 왼쪽 회전