[Python] collections.deque 모듈과 요세푸스 문제

Deque 자료형이란?

앞과 뒤에서 데이터를 처리할 수 있는 '양방향 자료형' 이다.

stack처럼 써도 되고, queue처럼 써도 됨

참고로 deque는 데크라고 읽는다.

 

collections.deque 모듈은 deque 자료형을 생성하는 모듈이다.

Deque 모듈의 메서드

appendleft(x)

말 그대로, 데크 왼쪽에 x를 추가하는 메서드이다.

from collections import deque

d = deque(range(0, 5))
d.appendleft(0)
print(d)

이런 출력이 나온다.

popleft()

데크 왼쪽에서 요소를 제거하는 메서드이다.

리스트에서는 첫 번째 요소를 제거할 때 pop(0) 을 사용하지만,

데크에서는 popleft()를 사용한다.

Deque의 장점

리스트 자료형과 비교했을 때, 데크 자료형이 갖는 장점은 바로 속도이다.

백준 11866, 요세푸스 문제

요세푸스 문제는 리스트 인덱스로도 접근할 수 있고 큐로도 접근할 수 있는데,

리스트로의 접근에 실패해서 큐로의 접근을 시도하였다.

deque를 통해 요세푸스 문제를 해결하였다.

문제를 해결하면서 사용한 것

Deque 자료형 생성하기

변수 이름 = deque(이터러블) 을 하면 deque형 변수를 생성할 수 있다.

from collections import deque

queue = deque(range(1, n + 1))

위 코드에서는 1부터 n까지의 연속된 수가 들어있는 deque형 변수 queue를 선언하였다.

변수를 사용하지 않는 반복문

이 코드를 작성하면서 새롭게 알게 된 사실이 있다.

그동안 파이썬에서 for문을 사용하면 꼭 for i in x와 같이 'i' 라는 변수를 반복의 지표로 사용해왔었다.

그런데 그런 변수가 필요 없고 그냥 반복만 하면 되는 상황이라면, '_', 언더바를 통해서 그런 상황을 표현해줄 수 있다.

for i in range(0, 4):
	print("안녕하세요 다섯번 네번 제창")

이런 식으로 코드를 작성해도 작동에는 전혀 문제가 없지만, 사용되지 않는 변수가 있기 때문에

이런 상황을 변수를 사용하지 않는 반복문의 사용을 통해 해결해 줄 수 있다.

for _ in range(3):
	print("hello?")

이런 식으로 변수를 사용하지 않는 단순 반복문을 만들어 줄 수 있다.

또한 range를 0에서 시작하도록 한다면 굳이 (0, 3) 과 같이 작성할 필요가 없이

(3) 만 써 주어도 된다.

위와 같이 코드를 작성하면 단순 반복시 가독성이 더 높아지는 효과가 존재한다.

11866 해결 코드의 핵심

이 문제를 처음 해결하고자 내가 작성한 코드는 다음과 같다.

n, k = map(int, input().split())
nums = list(range(1, n + 1))
k = k - 1  # 인덱스 숫자는 하나씩 작으니..
result = []
while True:
    result.append(nums.pop(k))
    nums = nums[k:] + nums[0:k]
    if len(nums) < k + 1:
        break
result = result + nums
print('<', end='')
print(*result, sep= ', ', end= '')
print('>', end='')

이 코드의 핵심은 nums 집합에서 k번째 숫자를 pop하여 result 리스트에 추가하고,

k번째와 뒤 숫자들 + 처음부터 k번째 전 숫자들을 합쳐 새로운 nums를 만들어 이를 반복하는 것이었다.

또한 마지막에는 nums 리스트의 길이가 k보다 작아지면 break한 뒤 그대로 남아있는 숫자를 뒤에 붙이도록 했다.

 

다음 코드는 nums의 길이가 k보다 작아졌을 때 다른 반례들에서 다른 답안을 출력했다.

문제의 요지는 남아 있는 숫자들을 그대로 붙이는 것이 아니라, k보다 남아 있는 숫자가 작아서 k번째 숫자를 뽑아내는 작업은 할 수 없더라도 숫자가 돌아 겹쳐도 'k번째' 숫자를 뽑아낸다는 원칙을 지켜야 한다는 것임을 알게 되었다.

 

따라서 이런 작업의 수행은 deque를 통해서 하는 것이 더욱 효과적일 것이라고 생각했다.

가장 앞에 있는 요소를 빼내서 뒤에 추가하는 작업을 k-1번 반복한 후,

k번째 수를 result 리스트에 추가하여 저장한다.

이 작업은 deque 자료형 변수에 값이 있을 때! True일때만 진행하도록 한다.

 

이런 내용을 반영하여 작성한 코드는 다음과 같다.

queue = deque(range(1, n + 1))
while queue:
    for _ in range(k - 1):
        queue.append(queue.popleft())
    result.append(queue.popleft())

 

이것이 핵심이고, 출력 시 sep 옵션을 사용하였는데 꽤나 유용하였다.

[파이썬] 복잡한 리스트 보기 좋게 출력하기