[백준] 2164번 카드2 (파이썬)

문제

2164번: 카드2

 

 

풀이 (Python)

 

from collections import deque
n=int(input())
queue=deque()
for i in range(1,n+1):queue.append(i)

while True:
    if len(queue)==1:
        break
    queue.popleft()
    queue.append(queue[0])
    queue.popleft()

print(*queue)

 

 

설명  (Python)

 

설명과 함께 첫 풀이 과정으로 풀이하겠다.

문제에서 제시한 것과 같이 for문을 통해 리스트에 1~n까지의 숫자를 넣어준다.

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

 

queue[0]이 가장 위라고 생각하고 문제에서 제시한 행동( 1. 맨 위의 카드를 버린다. / 2. 맨 위의 카드를 아래로 내린다.)  이 두 가지 행동을 반복하는 부분은 다음과 같이 간단하게 작성 가능하다.

queue.pop(0)
queue.append(queue[0])
queue.pop(0)

 

반복해야하기 때문에 while문에 위의 행동을 넣어서 코드를 완성하면 다음과 같다.

n=int(input())
queue=[]
for i in range(1,n+1):queue.append(i)

while True:
    if len(queue)==1:
        break
    queue.pop(0)
    queue.append(queue[0])
    queue.pop(0)

print(*queue)

하지만 이와 같이 풀이시에 시간초과가 발생한다.

 

 

keypoint 1- list와 deque의 시간복잡도 

list의 pop(0)의 경우 시간복잡도가 O(n)이지만 deque의 popleft()는 시간복잡도가 상수시간인 O(1)이다.

 

 

 

 

그러므로 list를 사용하여 queue로 작성하는 풀이가 아닌 deque를 활용하여 queue를 작성하여야한다.

 deque는 아래와 같이 import하여 사용할 수 있다.

from collections import deque
queue=deque()

 

list를 활용한 큐로 푼 풀이 코드에서 list대신 deque를 사용하고 pop(0) 대신 popleft()로 바꾸기만 하면 시간초과 문제는 간단하게 해결된다.

from collections import deque
n=int(input())
queue=deque()
for i in range(1,n+1):queue.append(i)

while True:
    if len(queue)==1:
        break
    queue.popleft()
    queue.append(queue[0])
    queue.popleft()

print(*queue)

 

 

큐의 자료구조 개념에 대해서는 아래의 글을 참조 하길 바란다.

[알고리즘] 자료구조 개념 / 스택, 큐, 덱, 힙 ( Stack, Queue, Deque, Heap)