[Python] 백준2164 카드2

22 Dec 2022 in Study on Algorithm

백준2164 카드2 링크

문제

예제 입력

---

코드

# O(1)
from collections import deque

dep = deque(x+1 for x in range(int(input())))

while len(dep) != 1:
    dep.popleft()
    dep.append(dep.popleft())
print(dep[0])

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 덱을 사용하여 양방향으로 삽입/삭제하여 최종적으로 남은 값을 출력합니다.

dq=deque() # 덱 생성
dq.append() # 덱의 가장 오른쪽에 원소 삽입
dq.popleft() # 가장 왼쪽 원소 반환
dq.appendleft() # 덱의 가장 왼쪽에 원소 삽입
dp.pop() # 가장 오른쪽 원소 반환
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) #x와 같은 원소의 개수를 계산

---

정리

# O(n)
n = int(input())
arr = [ i for i in range(1, n + 1)]

while len(arr) != 1:
    del(arr[0])
    arr.append(arr[0])
    del(arr[0])
    
print(arr[0])

처음에 풀었던 방식은 리스트를 활용해서 구현했는데 삽입/삭제할 때 알고리즘적으로 오래걸려 시간초과가 발생했습니다. 일반적으로 리스트를 사용하여 스택이나 큐를 사용하지 않습니다.

# O(1)
from queue import Queue, LifoQueue, PriorityQueue, SimpleQueue

queue = Queue()
for x in range(int(input())):
    queue.put(x+1)
        
while queue.qsize() != 1:
    queue.get()
    queue.put(queue.get())
    
print(queue.get())

덱만 아니라 자료형으로 큐를 사용하여 구현할 수 있습니다.

---

결과