백준, 카드2, 2164

[유형]

자료구조, 큐

 

[문제링크]

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)

 

[참고] https://github.com/VSFe/Algorithm_Study/blob/main/Concept/Prev/vol.2/01_Data_Structure/Ch.01_%EA%B8%B0%EB%B3%B8_%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0.pdf