[baekjoon]2164번 : 카드2 by python with deque(데큐)

https://www.acmicpc.net/problem/2164

2164번: 카드2

code 

 

#카드 2
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())

n = deque(range(1,N+1))

def card(n):
    while len(n)>1:
        n.popleft()
        n.append(n.popleft())
    print(n[0])

card(n)

 

 

시간초과 code

#카드 2
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())

n = deque(range(1,N+1))

def card(n):
    while len(n)>1:
        n.popleft()
        n.append(n.popleft())
    print(n[0])

card(n)

처음 푼 코드는 list를 사용하였는데 시간초과가 떴다.

이것저것 바꿔보았는데 여전히 해결이 안돼 찾아본 결과 이 문제는 데크 (deque)를 해결하여 풀어야했다.

 

데크(deque)개념은 처음이라 아래 블로그를 보며 공부를 했다.

https://leonkong.cc/posts/python-deque.html

Python - 데크(deque) 언제, 왜 사용해야 하는가?

 

데크는 양뱡향 큐인데 양끝 요소의 append와 pop이 상당히 빠르기때문에,

 

2164번같이 양끝 요소를 건들여 해결하는 문제에 사용하는 개념이다.

시간복잡도는 리스트가 O(n)이 소요되는데에 비해 데큐는 O(1)이다.

 

데큐 사용법은 다음과 같다.

from collections import deque

deq = deque()
deq.appendleft(10)
#시작부분에 10추가
deq.append(10)
#끝부분에 10추가
deq.popleft()
#시작요소 삭제
deq.pop()
#끝 요소 삭제

시작점과 끝점을 관리할때는 데큐가 리스트에 비해 월등히 우수 함으로 해당 문제들에 대해서 자주 활용해야겠다.