백준 2164. 카드2

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

2164번: 카드2

카드가 한 장 남을때까지 반복하는 과정이다.

우선 제일 위에 있는 카드는 버린다.

그 다음 제일 위에 있는 카드는 제일 아래에 있는 카드 밑으로 옮긴다.

그 과정을 반복하면 마지막 한장이 남는데 그 카드의 숫자가 무엇인지 출력하는 문제이다.

 

이 과정을 queue를 이용해 풀어본다.

파이썬은 리스트가 큐의 역할을 흉내내고 있어 리스트로 풀어본다.

import sys

nums = int(sys.stdin.readline())

queue = [ i for i in range(1, nums+1)]

while len(queue) != 1:
    queue.remove(queue[0])

    n = queue.pop(0)
    queue.append(n)

print(queue.pop())

* pop은 맨 뒤의 요소를 꺼내기 때문에 remove을 이용해 해당 값을 꺼낸다.

* 또 다시 맨 앞의 원소를 꺼내 맨 뒤에 삽입한다.

 

결과는 시간초과!

 

deque로 다시 구현해본다.

deque는 앞과 뒤 모두 요소를 빼고 삽입 할 수 있는 특징을 가지고 있다.

from collections import deque
import sys

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

while len(queue) != 1:
    queue.popleft()
    n = queue.popleft()
    queue.append(n)

print(queue.popleft())

* remove 대신 popleft 함수를 이용해서 바로 앞의 원소를 꺼내줬다.