[python] 2164. 카드2

• 문제

---

 

 

 

• 잘못된 풀이 

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

num_list = [i for i in range(1,N+1)]
# print(num_list)

while len(num_list) > 1:
    num_list.pop(0) # 맨 위에 있는 원소 pop
    number = num_list.pop(0) # 두번째 있는 원소 pop하고 마지막에 붙이기
    num_list.append(number)

    if len(num_list) == 1:
        print(num_list[0])

 

나는 해당 문제를 queue의 자료구조를 생각하며 풀었다.

문제는 쉽게 풀 수 있었지만, 결과적으로 시간초과로 문제풀이에 실패하였다.

 

 

 

 

• 올바른 풀이 

import sys
from collections import deque

N = int(sys.stdin.readline())
deque = deque([i for i in range(1, N+1)])

while len(deque) > 1:
    deque.popleft()
    number = deque.popleft()
    deque.append(number)
print(deque[0])

 

queue의 자료구조 방법으로 해당 문제 풀이에 실패하였기 때문에,

queue보다 더 낮은 시간복잡도를 가지는 방법으로 문제를 해결해야 한다.

 

Collections, deque (Double Ended Queue) ?
파이썬에서 제공하는 모듈 중에, collections의 deque가 있다.
queue와 stack을 모두 만들 수 있는 자료구조로, 양 끝에서 모두 push와 pop이 가능하다.
deque는 CPython으로 구성되어 있기 때문에, queue보다 훨씬 빠르다. 

 

이렇게 queue보다 빠른 deque로 문제를 해결할 수 있었다.