태야

<내 코드>

from collections import deque
n = int(input())
nums = deque()

for i in range(1, n+1):
    nums.append(i)


def que():
    cnt = 0
    while(len(nums) >= 1):
        cnt += 1
        if(len(nums) == 1):
            return nums[0]

        if(cnt % 2 == 1):
            nums.popleft()

        elif(cnt % 2 == 0):
            nums.append(nums.popleft())


print(que())

처음에 deque 사용하지 않고 pop() 2개를 사용했더니 역시나 시간 초과가 났다.. 

카운트를 이용해 홀수, 짝수 순서에 따라 카드 제거 & 카드 뒤로 이동을 구현했다.

<내 코드>

import sys
from collections import deque

n = int(sys.stdin.readline())
deque = deque()


def push(queque, x):
    deque.append(x)


def pop(deque):
    if(not deque):
        return -1
    else:
        return deque.popleft()


def size():
    return len(deque)


def empty():
    if(not deque):
        return 1
    else:
        return 0


def front():
    if(not deque):
        return -1
    else:
        return deque[0]


def back():
    if(not deque):
        return -1
    else:
        return deque[-1]


for i in range(n):
    oper = sys.stdin.readline().split()

    if (oper[0] == "push"):
        push(deque, oper[1])
    elif(oper[0] == "pop"):
        print(pop(deque))
    elif(oper[0] == "size"):
        print(size())
    elif(oper[0] == "empty"):
        print(empty())
    elif(oper[0] == "front"):
        print(front())
    elif(oper[0] == "back"):
        print(back())

이 문제는 시간 복잡도가 O(1)이 되어야 하는데, 일반적인 리스트의 pop() 함수를 사용하면 첫 번째 요소를 pop 할 때는 O(n)의 시간이 소요된다. 그래서 collections의 deque를 사용했다. pop 부분에서 popleft를 이용해 시간을 단축시킬 수 있다. deque는 스택과 큐를 합친 자료구조이다.