[Python]백준 BaekJoon.AC 2164 : 카드2(deque, queue)

 

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

2164번: 카드2

 

 

 

알고리즘 분류가 큐인데.. 큐로 풀었더니 틀림처리 된다... 이유는 시간초과.

(큐로 다른 풀이법이 있는건가..)

 

 

<틀린 코드>

import queue

N = int(input())
que = queue.Queue()

for i in range(N):
    que.put(i+1)

while que.qsize() != 1:
    que.get()
    que.put(que.get())

print(que.get())

 

 

아마 put과 get 처리가 오래 걸려서 그런 것 같단 추측을 해보지만... deque 코드와 크~~게 다를 건 없어보이지만...

아무튼 덱을 써야 한다!^^

append와 pop 함수는 용도를 쉽게 추측할 수 있겠지만 rotate함수는 어려울 수 있다.

나도 원래 pop과 append를 이용해 rotate 함수와 같은 기능을 구현하려 하였으나, 새로운 함수가 있길래 사용해봤다.

 

무엇보다 코드로 이해하는 편이 쉽다.

 

deq = deque([1, 2, 3, 4, 5])

deq.rotate(1)
print(deq)
출력 : deque([5, 1, 2, 3, 4])

deq.rotate(-1)
print(deq)
출력 : deque([1, 2, 3, 4, 5])

 

 

 

from collections import deque

N = int(input())
deq = deque()

for i in range(N):
    deq.append(i+1)

while len(deq) != 1:
    deq.popleft()
    deq.rotate(-1)

print(deq.pop())

 

+)이 방법 말고도.. 홀수번째 숫자만 계속 지우는 방법을 떠올려봤는데, 실행을 안해봐서 가능한진 잘 모르겠다.

옳은 방법인지도 확신할 수 없지만 가능하다면 멋진 방법이 될 듯 하며 시간은 초과될 것 같다ㅎ

리스트와 del을 사용해야 하기 때문... del은 시간이 오래걸린다.