ETC/Algorithm
백준, 카드2, 2164
coding_genie
2024. 8. 12. 23:25
[유형]
자료구조, 큐
[문제링크]
https://www.acmicpc.net/problem/2164
[요약]
- N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여있다.
- 카드가 한 장 남을 때까지 다음 동작을 반복한다. 제일 위에 있는 카드를 바닥에 버린다. 다음 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
- N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
[제약조건]
N(1 ≤ N ≤ 500,000)
[문제풀이]
N=4인 경우,
1234 => 234 => 342 => 42 => 24 => 4
순서대로 처리해야하는 일을 수행할 때.
처리 과정에서 데이터를 제거해야하는데, 제거해야하는 위치가 맨 끝이 아닐 때.
deque()를 사용한다.
import sys
from collections import deque
def input():
return sys.stdin.readline().rstrip()
N = int(input())
queue = deque()
for i in range(1,N+1):
queue.append(i)
while True:
a = queue.popleft()
if not queue:
print(a)
break
b = queue.popleft()
queue.append(b)