[Do-it! 코딩 테스트-기초편] 013. 카드 게임

문제

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

2164번: 카드2

---

접근

데이터 크기: 500,000

시간 제한: 2초

 

반복문 안에서 리스트 insert() 메서드를 사용하거나 리스트 조작을 하면 시간이 초과될 수 있다.

큐와 스택의 성질을 사용하면 쉽게 시간에 제약을 받지 않고 구현할 수 있다.

큐와 스택의 성질을 동시에 사용이 가능한 덱(Deque)을 사용해보자.

---

코드

from collections import deque

N = int(input())

dq = deque(list(range(N, 0, -1)))
temp = []
while True:
    if len(dq) == 1:
        break
    dq.pop()
    dq.appendleft(dq.pop())


print(dq[0])

---

설명

Deque를 직접 생성할 수도 있겠지만 파이썬은 deque 모듈을 제공한다.

N부터 1까지의 deque를 생성하여 맨 윗장을 pop하고 그 다음 맨 윗 장을 pop함과 동시에 appendleft한다.

만약 덱에 원소가 하나 남으면 반복문을 탈출하고 출력한다.

---

알고리즘

덱(Deque)

큐(Queue)

스택(Stack)