[백준알고리즘] 2164번: 카드2 -Python

[백준알고리즘] 2164번: 카드2 -Python

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

2164번: 카드2

 

큐를 이용한 문제를 푸는 것이다.

 

파이썬으로 큐 모듈이 있던 것 같아서 찾던 와중에 쓰기 좋은 것을 찾았다.

바로 collections의 deque이다.

 

 

deque는 '덱'이라고 하며 Double Ended Queue의 약자이다. 큐와 스택을 둘 다 만들 수 있는 자료구조인데, 양 끝단에서 모두 push, pop이 가능하다. 

 

 

파이썬에서 collections모듈 안의 deque는 CPython으로 구성되어 있어서 속도면에서 훨씬 빠르다고 한다. 일반적인 Queue.Queue는 멀티스레딩을 위한 큐로 사용되어서 이렇게 일반적인 알고리즘 문제를 푸는 데에 있어서는 collections.deque를 사용하는 것이 바람직하다고 한다. 그리고 Queue.Queue가 내부적으로 collections.deque를 사용한다고 한다.

 

두 개의 목적이 다르니 맞춰서 사용하는 것이 좋을 것 같다.

링크

 

 

collections.deque의 기본적인 함수들은 여기서 확인하면 될 것 같다.

 

그리고 deque의 길이를 확인할 때에는 그냥 리스트처럼 len(deque)를 사용해주면 된다고 한다.

이걸 알게 되면서 len()이 object의 __len__을 호출한다는 것도 알게 되었다.

링크

 

 

이 문제를 두 가지 방법으로 풀어봤다. 하나는 위에서 언급한 collections.deque를 사용한 방법과 다른 하나는 문제의 속성을 이용해서 queue를 사용하지 않고 리스트만으로 푼 것이다.

 

먼저 deque를 사용한 풀이 방법이다.

 

import sys
from collections import deque

N = int(sys.stdin.readline())
queue = deque()

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

while len(queue) > 1:
    queue.popleft()
    queue.append(queue.popleft())

print(queue.pop())

 

deque를 사용하지 않고 푼 방법이다.

여기서 슬라이싱 부분에 보면 [start : end : term]이라고 보면 된다.

즉 1번 index부터 2칸씩 챙겨오니, 짝수번째 값들만 가져오는 것이다.

 

import sys

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

arr = [i+1 for i in range(N)]

while len(arr) > 1:
    if len(arr) % 2:
        t = [arr[-1]]
        t.extend(arr[1::2])
        arr = t
    else:
        arr = arr[1::2]
        

print(arr[0])

 

두 개의 코드 중에서는 밑의 방법이 조금 더 빠른 속도가 나오긴 했는데, 이러한 특징 없이 큐를 사용할 때에는 deque를 사용해야겠다.

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다