[백준] 2164번 : 카드2

문제

깨달은 점

계속 시간초과가 떴는데, 파이썬 라이브러리 중 collections의 deque를 활용헤서 코드를 구현해서 해결할 수 있었다.

deque는 list보다 속도가 빨라서 pop(0)와 같은 메서드를 수행할 때 리스트의 경우 O(N)연산을 수행하지만 deque는 popleft()와 같은 메소드를 활용하여 O(1) 연산을 수행하기 때문이다.

deque은 아래와 같은 추가 메소드들이 있다.

appendleft(n) : 맨 앞에 데이터 n 입력하기
popleft() : 맨 앞에 있는 데이터 내보내기

개념

시간초과를 해결하기 위해 deque 자료형을 이용해야 했다.

deque(데크)

양방향 큐처럼 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있는 자료구조

즉 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있으므로 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다!

컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.

from collections import deque

deq = deque([1,2,3,4,5])

# 맨 앞에 데이터 입력
deq.appendleft(0) # deque([0, 1, 2, 3, 4, 5])

# 맨 뒤에 데이터 입력
deq.append(6) # deque([0, 1, 2, 3, 4, 5, 6])

# 맨 앞에 있는 데이터 출력
deq.popleft() # deque([1,2,3,4,5,6])

# 맨 뒤에 있는 데이터 출력
deq.pop() # deque([1,2,3,4,5])

# item을 데크에서 찾아 삭제한다.
deque.remove(item)

리스트에서 n만큼 회전하는 문제

deq.rotate(n)

deque(a)로 deque객체를 만든 후 rotate함수를 사용하여 2만큼 우측으로 회전하였다.
만약 좌측으로 2만큼 회전한다면 2대신 -2를 입력하면 된다.

from collections import deque
a = [1, 2, 3, 4, 5]
q = deque(a)
q.rotate(2)
result = list(q)
result
[4, 5, 1, 2, 3]

cf.

스택

LIFO (last in first out)
나중에 넣은 데이터가 먼저 반환되도록 설계한 메모리 구조

데이터의 입력은 push > append()
출력은 pop > pop()

리스트를 사용하여 스택 구조로 데이터 처리 가능

큐

FIFO(first in first out)
줄이라는 의미로, 먼저 줄 선 데이터가 먼저 반환되도록 하는 것

역시 리스트를 사용하여 구현하며
입력 push > append()
출력 get > pop(0)
가장 먼저 있는 0번째 원소를 뽑아냄!!

참고사이트 : https://leonkong.cc/posts/python-deque.html
https://wikidocs.net/104977

정답 풀이

import sys
from collections import deque

N = int(sys.stdin.readline())

numlist = []

for i in range(N):
    numlist.append(i+1)
    
deq = deque(numlist)

if N == 1:
    print(numlist[0])
elif N == 2:
    print(numlist[1])
else:
    for i in range(N-2):
        deq.popleft()
        num = deq.popleft()
        deq.append(num)
    print(deq[1])

시간 초과 풀이

import sys
N = int(sys.stdin.readline())

numlist = []

for i in range(N):
    numlist.append(i+1)

if N == 1:
    print(numlist[0])
elif N == 2:
    print(numlist[1])
else:
    for i in range(N-2):
        numlist.pop(0)
        num = numlist.pop(0)
        numlist.append(num)
    print(numlist[1])