bj2156 카드

이 문제는 Queue에 관한 문제이다. queue를 구현해서 할 수도 있지만 그냥 module에서 구현된 deque를 써서 간단하게 구현했다.
사실 stack은 list로 queue는 deque를 이용하면 더 간단하다! 속도차이가 거의 없기 때문에 굳이 새로운 자료구조를 구현할 필요가...

로직은 다음과 같다
1. for loop 돌면서 enqueue
2. card 갯수 1개 남을 때까지 while loop돌리기
3. 첫 card 버리고 2번째 card deque한 것 enqueue로 넣어주기
4. 1개 남은 card print로 출력하기

근데 아... 복붙을 잘못해서 runtime error를 몇 번 내는 건지 모르겠다.
요세푸스 문제 풀 때도 그랬는데..
collections에서 deque를 import하는 문장을 빼고 복붙을 해서 런타임 에러뜸...

from collections import deque

N = int(input())
deq = deque([])
for i in range(1, N+1):
    deq.append(i)

while len(deq) != 1:
    deq.popleft()
    deq.append(deq.popleft())

print(deq[0])

만약 Queue로 구현하려면 같은 로직으로

class Node:
    def __init__(self, data = None):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def enqueue(self, data):
        node = Node(data)
        self.size += 1
        if self.size == 0:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dequeue(self):
        if self.size == 0:
            return None
        self.size -= 1
        data = self.head.data
        self.head = self.head.next
        return data

를 이용하면 된다.