2164 : 카드2

• 백준 url

• 실버 4

시간제한	메모리제한	정답비율
2초	128MB	50.9%

input

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

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

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

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
1<=N<=500,000 6->4

from collections import deque
import os, sys


def step1(dq):
    dq.popleft()
    return dq

def step2(dq):
    dq.rotate(-1)
    return dq

problem_num = 2164
path = os.getcwd() + f'\\txt\\{problem_num}'  + '.txt'
sys.stdin = open(path,'r')
input = sys.stdin.readline()
n = int(input)
n_dq = deque([i for i in range(1,n+1)])
while len(n_dq) != 1:
    n_dq = step1(n_dq)
    n_dq = step2(n_dq)
print(*n_dq)

if n_dq[0] == 4:
    print('right')
else:
    print('wrong')

4
right

Deque : double-ended queue

from collections import deque
dq = deque()
dq.append([i for i in range(n)])

• 스레드 안전하고 메모리 효율적인 데크의 양쪽 끝에서의 추가(append)와 팝(pop)을 양쪽에서 거의 같은 O(1) 성능으로 지원한다. 일반적인 리스트는 O(n) 메모리 이동 비용

• max len이 지정되어 있으면 항목이 추가될 때마다 반대쪽 끝에서 삭제된다.

• stack처럼 사용할수도 있고, queue처럼 사용할수도 있다.

method	do
append	데크의 오른쪽에 x를 추가합니다.
appendleft(x)	데크의 왼쪽에 x를 추가합니다.
clear()	데크에서 모든 요소를 제거하고 길이가 0인 상태로 만듭니다.
copy()	데크의 얕은 복사본을 만듭니다.
count(x)	x 와 같은 데크 요소의 수를 셉니다.
extend(iterable)	iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장합니다.
extendleft(iterable)	iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장합니다.일련의 왼쪽 추가는 iterable 인자에 있는 요소의 순서를 뒤집는 결과를 줍니다.
index(x[, start[, stop]])	데크에 있는 x의 위치를 반환합니다 (인덱스 start 또는 그 이후, 그리고 인덱스 stop 이전). 첫 번째 일치를 반환하거나 찾을 수 없으면 ValueError를 발생시킵니다.
insert(i, x)	x를 데크의 i 위치에 삽입합니다.삽입으로 인해 제한된 길이의 데크가 maxlen 이상으로 커지면, IndexError가 발생합니다.
pop()	데크의 오른쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, IndexError를 발생시킵니다.
popleft()	데크의 왼쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, IndexError를 발생시킵니다.
remove(value)	value의 첫 번째 항목을 제거합니다. 찾을 수 없으면, ValueError를 발생시킵니다.
reverse()	데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환합니다.
rotate(n=1)	데크를 n 단계 오른쪽으로 회전합니다. n이 음수이면, 왼쪽으로 회전합니다.데크가 비어 있지 않으면, 오른쪽으로 한 단계 회전하는 것은 d.appendleft(d.pop())과 동등하고, 왼쪽으로 한 단계 회전하는 것은 d.append(d.popleft())와 동등합니다.
maxlen	(attribute)데크의 최대 크기 또는 제한이 없으면 None.