[파이썬&알고리즘] Queue의 개념과 백준 12873

큐(Queue)란?

• 입출력의 방향이 다른 자료구조.
• 처음 들어간게 처음으로 나오는 FIFO 구조를 가지고 있다.
  (현실에서 맛집 줄서기를 생각하면 된다. 먼저 온 사람이 가게에 먼저 들어가는,,)
• 기본연산
  1. Enqueue : 큐에 새로운 아이템 추가 O(1)
  2. Dequeue : 가장 먼저 들어갔던 아이템 제거 O(1)
  3. Front : 큐의 처음 데이터 확인
  4. Rear : 큐의 마지막 데이터 확인
• 트리나 그래프에서 많이 사용되는 개념이다.

파이썬에서 사용하기

• 파이썬에서는 네 가지 방법으로 큐를 사용할 수 있는데 보통 collections.deque 클래스를 사용한다.

1. 리스트로 append(), pop()하기
   • 동작은 잘 하는데 아주 느리고 정말 비효율적이다.
2. collections.deque 클래스
3. queue.Queue 클래스
4. multiprocessing.Queue 클래스
   => 1번은 아주 비효율적이고 3,4번은 코딩테스트에서 잘 사용하지 않는다고 한다.

collections.deque

• from collections import deque를 선언해서 사용한다.
• 기본연산
  1. Enqueue : 큐.append() - 제일 끝에 추가된다.
  2. Dequeue : 큐.popleft() - 가장 앞에 있는게 삭제된 배열을 반환한다.
  3. Front : 큐[0]
  4. Rear : 큐[-1]
  =>리스트 처럼 사용 가능하다.
• 큐 만들기

    from collections import deque
    queue_name = deque([1,2,3,4,5,6])

rotate

• 큐의 요소들을 매개변수의 값 만큼 회전해주는 메소드! (배열 안의 순서가 바뀜)
• 값이 음수면 왼쪽으로, 값이 양수면 오른쪽으로 이동한다.
• 음수일 경우 예시

 from collections import deque

queue =deque([i for i in range(1,7) ])

#큐의 기본 값
print(queue)
# deque([1, 2, 3, 4, 5, 6])

#왼쪽에 있는 값 하나를 오른쪽으로 이동
queue.rotate(-1)
print(queue)
# deque([2, 3, 4, 5, 6, 1])

#위의 큐에서 왼쪽에 있는 두개(2,3)을 오른쪽으로 이동
queue.rotate(-2)
print(queue)
# deque([4, 5, 6, 1, 2, 3])

#위의 큐에서 왼쪽에 있는 세개(4,5,6)을 오른쪽으로 이동
queue.rotate(-3)
print(queue)
# deque([1, 2, 3, 4, 5, 6])
       

• 양수일 경우 예시

import sys
from collections import deque

queue =deque([i for i in range(1,7) ])

#큐의 기본 값
print(queue)
# deque([1, 2, 3, 4, 5, 6])

#오른쪽에 있는 값 하나를 왼쪽으로 이동
queue.rotate(1)
print(queue)
# deque([6, 1, 2, 3, 4, 5])


#위의 큐에서 오른쪽에 있는 두개(4,5)을 왼쪽으로 이동
queue.rotate(2)
print(queue)
# deque([4, 5, 6, 1, 2, 3])


#위의 큐에서 오른쪽에 있는 세개(1,2,3)을 왼쪽으로 이동
queue.rotate(3)
print(queue)
# deque([1, 2, 3, 4, 5, 6])

이정도를 알면 큐 기본은 뗀 것이다!
이제 백준 문제를 풀어보자.

백준 12873문제
큐를 이용해서 푸는 문제다.

문제 속 힌트

1. 원을 이루어서 앉아있다. -> 원형 큐
2. 제거된 후에는 다음 사람에게 이동한다. -> 게임이 한 번 끝날때마다 시작점이 달라짐

예제 예시

• 6명일 경우 5단계를 거쳐야지 1명이 남게된다.
  시작 순서 : 123456
  1단계 1번째 사람 탈락, 티셔츠 번호 1번 지목순서 : 23456
  2단계 3번째 사람 탈락, 티셔츠 번호 4번 지목순서 : 5623
  3단계 3번째 사람 탈락, 티셔츠 번호 2번 지목순서 : 356
  4단계 1번째 사람 탈락, 티셔츠 번호 3번 지목순서 : 56
  5단계 1번째 사람 탈락, 티셔츠 번호 5번 지목순서 : 6

풀이

1. 참가자 인원의 티셔츠 번호를 큐에 담아서 큐로 처리한다.
2. 참가자 인원 - 1 만큼 게임을 진행할 수 있게 반복처리한다.
3. 탈락자는 단계의 세제곱 % 참가자 수를 큐 순서에 대입해서 탈락자를 정한다.
4. 탈락자는 dequeue하기 위해 맨 앞에 와있어야한다.(티셔츠 번호가 담긴 큐의 순서를 조정해야함)
5. 탈락자가 발생할 때마다 단계를 한단계씩 높이고 다시 게임을 진행한다.
6. 게임이 끝나면 남아있는 티셔츠 번호를 출력한다.
7. 예외) 탈락자를 구하는 나머지가 1인 경우 큐의 순서를 조정할 필요가 없다.

코드

정답 코드는 여기서 확인할 수 있다.