1. 큐(Queue)

Queue는 '대기 행렬, 줄을 서서 기다리다' 라는 뜻처럼 먼저 들어온 데이터가 먼저 나갈 수 있도록 되어있는 'FIFO:First In First Out', 선입선출 형식의 자료구조를 이야기한다. 후입선출(First In Last Out) 자료구조인 stack과 반대되는 구조이다. 예로 버스를 타기 위해 줄을 설 때 먼저 온 사람이 먼저 탈 수 있는 구조와 같이, 데이터를 다룰 때 먼저 들어온 데이터를 먼저 내보낼 때 사용한다.
한쪽이 막혀있어 입구와 출구가 하나인 것이 stack이라면, 입구와 출고가 따로 있는 것이 Queue이다.
큐(Queue)는 Linked List(연결 리스트)로 구현이 되는데 파이썬에서 이 큐 자료형을 위해 deque()함수를 제공하고 있으니 import로 쉽게 사용이 가능하다.

리스트 자료구조가 있는데 왜 굳이 큐를?

큐의 특징을 살펴보면 이런 질문이 가능하다. '굳이 함수를 내려받을 필요없이, Array List인 리스트로 자료를 입력 받고 데이터를 출력할 때는 제알 앞 인덱스를 꺼내오면 되지 않느냐? 굳이 어렵게 큐라는 자료구조를 알아야 하는가?'라고.
이것에 대해 자세히 이야기 하려면 Linked List의 구현부터 시작해서 자세히 설명해야하는데, 문제풀이에 좀 더 집중하기 위해 깊게는 들어가지 않고 설명하겠다. 연결 리스트(Linked List)는 배열 리스트(Array List)와 달리 하나하나의 데이터가 'Node'라 불리는 곳에 저장된다. 사실 데이터는 메모리에 저장되고 Node에는 데이터의 메모리 주소가 할당된다. 데이터가 차례로 들어올 때 제일 첫 노드를 Head 노드라고 하는데, Head 노드에 데이터가 담겨있고, 다음 데이터가 들어오면 새로운 노드가 생성된다. 이 생성될 때 Head 노드는 다음 노드를 가리킨다.(다음 노드의 메모리 주소를 가리킨다) 세 번재 노드가 들어오면 두 번째 노드가 세번째 노드를 가리키는 형식으로써, 순서로 배열되어 있는 것이 아니라 다음 노드를 가리키는 논리적 순서를 가지게 된다.
그래서 Linked List는 제일 앞의 것을 빼낼 때 Head 노드를 두 번째 노드로 바꾸고 Head 노드였던 자료는 큐에서 빠져나온다. 이는 빅오 표기법에 따라 상수 시간(O(1))을 가지는 매우 빠른 연산이 가능한 반면, Array List인 리스트는 순서대로 배열되어 있기에 0번 index가 빠져나오게 되면 0번 index를 순서상으로 채워야 하기에 1번 index부터 마지막 index까지 1번씩 index를 앞으로 옮겨야 하는 연산이 일어난다. 이는 빅오 표기법에 따라 선형 시간(O(N))의 연산이 일어난다.
쉽게 말해 선입선출의 방식으로 문제를 해결해야 할 때, 리스트는 N번의 연산을 하고 큐는 1번의 연산만 하기에 연산 횟수에서 차이가 난다. 그래서 큐 자료구조로 알고리즘을 문제를 해결해야 할 때 리스트를 사용하게 되면 시간 초과에 걸릴 수도 있다는 점을 유의하자.

2. 문제

그럼 큐라는 자료형을 어떻게 사용하는지 문제를 살펴보자.

용배와 친구들은 '007 게임'을 하려한다. 번호표를 가진 n 명의 친구들이 원탁자에 앉아서 게임을 하는데, 1번부터 시작해서 "0, 0, 7, '빵'" 소리를 왜치며 4번째 친구가 빵을 외치면 그 다음 5번인 친구는 탈락하게 되고 6번부터 다시 '0, 0, 7, '빵'을 하게 되면 10번 친구가 탈락한다. 이렇게 게임을 k회 했을 때 마지막에 탈락한 친구 다음 번호를 출력하는 프로그램을 작성하시오.
번호는 1번부터 시작되며 1명이 살아남을 시 살아남은 친구의 번호가 정답이되고 게임은 중단된다. n, k는 공백을 두고 입력된다.
예시) 10명의 친구, 게임을 3회 진행한다면,
입력 : n = 10, k = 3(2 < n <= 10,000, 2 < k <= 100)
1, 2, 3, 4, 6, 7, 8, 9, 10 <- 첫 번째 게임이 끝나고 살아남은 친구(1번시작 5번 탈락)
1, 2, 3, 4, 6, 7, 8, 9 <- 두 번째 게임이 끝나고 살아남은 친구(6번 시작, 10번 탈락)
1, 2, 3, 4, 7, 8, 9 <- 세 번째 게임이 끝나고(1번 시작, 6번 탈락)
출력: 7

3. 풀이

5번째 순서의 친구를 계속해서 탈락시켜 나가는 게임이다.
원형탁자에서 계속 돌아가며서 탈락되는데 그것을 코드에서 구현하기 위해서 5번째가 아닌 친구의 순서가 되면 마지막 자리로 옮겨주면 된다.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 시작
[2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 첫 번째 게임 1회: 0
[3, 4, 5, 6, 7, 8, 9, 10, 1, 2] 첫 번째 게임 1회: 0
[4, 5, 6, 7, 8, 9, 10, 1, 2, 3] 첫 번째 게임 1회: 7
[5, 6, 7, 8, 9, 10, 1, 2, 3, 4] 첫 번째 게임 1회: 빵
[6, 7, 8, 9, 10, 1, 2, 3, 4] 첫 번째 게임 1회 탈락한 친구는 5번
이렇게 원형탁자에 앉아있기에 계속 진행하려면 탈락이 되지 않은 친구는 제일 뒤쪽 순서로 넣어주면 된다.
k회가 진행된 후 제일 앞의 친구 번호가 정답이다.

from collections import deque # 큐자료형 deque 사용.
n, k = map(int, input().split()) # 공백을 사이에 두고 n, k를 입력 받는다.
friend = []
for i in range(1, n + 1):
    friend.append(i) # 1번부터 시작하여 n명의 친구들의 번호를 순서대로 리스트에 입력한다.
dQ = deque(friend) # 입력된 리스트를 큐 자료형으로 변환한다.
for i in range(k): # k회 반복
    for j in range(4): # 4번 반복 후 5번째 친구를 탈락
        if len(dQ) > 1: # 1명만 이상일 때는 게임을 지속하다, 1명이 남을 경우 1명 남은 친구가 정답이기에 출력하고 반복문을 중단한다.
            x = dQ.popleft()
            dQ.append(x)
        else:
            print(dQ.popleft())
            break
    dQ.popleft() # 4번의 007이 지나가고 5번째 친구는 빼내기만 해서 탈락시킨다.
else:
    print(dQ.popleft()) # 반복문이 정상적으로 끝났다면(게임이 끝났다면) 제일 처음 나오는 친구 번호가 정답.

4. deque

주로 쓰이는 deque의 메서드

from collections import deque
dQ = deque()

1. dQ.popleft() : dQ에서 제일 앞의 데이터 꺼내기.
2. dQ.append(i) : dQ에서 제일 뒤에 데이터 i 넣기.
3. dQ.pop() : dQ에서 제일 뒤의 데이터 꺼내기.
4. dQ.appendleft(i) : dQ에서 제일 앞에 데이터 i 넣기.