[백준] 2164 : 카드2 / 파이썬 / 자료구조 / 큐

💻 문제

자료구조 / 큐 문제에 해당하는 '2164 : 카드2' 문제

---

💡 코드

초기 코드

numList=[]

N=int(input())
for i in range(N,0,-1):
    numList.append(i)
  

while len(numList) != 1:  
    numList.pop()
    next=numList.pop()
    numList.insert(0,next)

print(numList)

처음에는 list를 사용해 코드를 구현하였으나, 시간초과가 발생했다. 그래서 list보다 연산 속도가 빠른 deque를 사용해서 문제를 해결하였다.

정답 코드

from collections import deque

N=int(input())
myqueue = deque()

for i in range(N,0,-1):
    myqueue.append(i)

while len(myqueue) != 1:
    myqueue.pop()
    next = myqueue.pop()
    myqueue.appendleft(next)
print(myqueue[0])

---

📚 해결 과정

list를 사용하여 구현하였을 때에는 맨 위에 있는 카를 pop()을 사용해서 버리고 그 다음 위에 있는 카드를 insert() 함수를 사용하여 list의 앞쪽에 추가하는 방식을 택하였다.

list는 고정된 배열이기 때문에 의 앞쪽에 데이터를 삽입하는 과정에서 O(n) 만큼의 시간 복잡도가 발생하여 시간 초과가 발생하는 문제가 있었다.

데이터를 앞이나 중간에 삽입할 때에는 dequeue와 같은 구조의 자료구조를 사용해줌으로써 시간 복잡도를 줄일 수 있다.

내부적으로 dequeue는 double linked list 구조로 구현되어있어서 앞이나 뒤에 데이터를 삽입, 삭제할 때에도 O(1)의 시간복잡도가 걸리게된다.

list와 dequeue의 시간복잡도 및 내부 구현에 관련해서는 아래 링크를 통해 정리해놨다.
(링크 추가 예정)

---

💪🏻 TIL

시간복잡도를 고려하여 어떤 자료구조를 사용하는 것이 문제 해결에 적절할지 생각하는 습관을 가져야겠다.