[자료구조 알고리즘] 큐(Queue)

큐(Queue)는 한쪽 끝에서만 자료의 삽입,삭제가 가능한 선입선출 FIFO 형태의 선형 자료구조이다
스택(Stack)과는 달리 가장 먼저 삽입한 자료가 가장 먼저 반환되는 구조로 이루어진다.
줄의 첫 번째에 서 있는 사람이 먼저 서비스를 받고, 그 다음으로 줄에 선 사람이 서비스를 받는 식으로 생각하면 된다.

하지만 이렇게 list를 큐(Queue) 자료구조의 효과를 내기 위해서 사용하는 것은 추천되지 않고 있다.
파이썬의 list는 다른 언어의 배열처럼 무작위 접근에 최적화된 자료구조이기 때문에 pop(0), insert(0,x) 는 성능적으로 매우 불리한 연산이다.
이 두 연산의 시간 복잡도는 0(n)이기 때문에 담고 있는 데이터의 개수가 많아질 수록 느려진다.
첫 번째 데이터를 제거한 후에 그 뒤에 있는 데이터를 모두 한 칸씩 밀어줘야 하기 때문이다.

💡 deque

collections 모듈의 deque는 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.
deque는 list에는 없는 popleft()라는 메서드를 제공한다.
이 메서드를 사용하면 첫 번째 데이터를 제거할 수 있다.
데이터의 흐름은 list객체의 pop(0) 메서드를 사용할 때처럼 뒤에서 앞으로 흐르게 된다.
추가적으로 deque는 appendleft(x)라는 메서드도 제공한다.
해당 메서드는 데이터를 맨 앞에서 삽입할 수 있게 해준다.
이 경우, 데이터의 흐름은 list 객체의 insert(0,x) 메서드를 사용할 때 처럼 앞에서 뒤로 흐르게 된다.

deque의 popleft()와 appendleft(x) 메서드는 모두 0(1)의 시간 복잡도를 가지고 있기 때문에 list의 pop(0) 또는 insert(0,x) 대비 성능 상에 큰 이점이 있다.

deque의 단점도 존재한다.
바로 무작위 접근의 시간 복잡도가 0(n)이라는 것이다.
내부적으로 linked list를 사용하고 있기 때문에 i번째 데이터에 접근하려면 맨앞/뒤부터 i번 순회가 필요하기 때문이다.

card2

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

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입력 1
6
예제 출력 1
4

from collections import deque

def solution_queue(num):
    # cards(deque)를 이용하여 1부터 num까지의 카드를 deque에 저장
    cards = deque([i for i in range(1, num+1)])
    while len(cards) > 1:
    # 카드가 한장 남을때까지(1 이하가 될때까지) 반복한다.
        cards.popleft()
    # 제일 위에 있는 카드를 버린다. popleft() 메서드 사용 / 1을 버리면 234가 남는다
        cards.append(cards.popleft()) # *버리는 카드를 append()로 뒤에 붙임
    # 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
    # 2를 제일 아래로 옮기면 342가 된다. 다시 while문에 의해 3을 버리면 42가 되고
    # 4를 밑으로 append()옮기면 24가 된다 마지막으로 2를 버리고 나면 남는 카드는 4가 된다 .
    return cards.popleft()
    # 마지막 남은 카드를 반환한다.

# 함수 출력
num = 7 # 다른 입력 예시
result = solution_queue(num)
print(result)
# 6

첫 번째 처리: 현재 카드 상태: [1, 2, 3, 4, 5, 6, 7]
제일 위에 있는 카드 1을 버린다.
남은 카드: [2, 3, 4, 5, 6, 7]
다음, 카드 2를 맨 아래로 옮깁니다.
현재 카드 상태: [3, 4, 5, 6, 7, 2]
두 번째 처리: 현재 카드 상태: [3, 4, 5, 6, 7, 2]
제일 위에 있는 카드 3을 버린다.
남은 카드: [4, 5, 6, 7, 2]
다음 카드 4를 맨 아래로 옮긴다.
현재 카드 상태: [5, 6, 7, 2, 4]
세 번째 처리: 현재 카드 상태: [5, 6, 7, 2, 4]
제일 위에 있는 카드 5를 버린다.
남은 카드: [6, 7, 2, 4]
다음 카드 6을 맨 아래로 옮긴다.
현재 카드 상태: [7, 2, 4, 6]
네 번째 처리: 현재 카드 상태: [7, 2, 4, 6]
제일 위에 있는 카드 7을 버린다.
남은 카드: [2, 4, 6]
다음 카드 2를 맨 아래로 옮긴다.
현재 카드 상태: [4, 6, 2]
다섯 번째 처리: 현재 카드 상태: [4, 6, 2]
제일 위에 있는 카드 4를 버린다.
남은 카드: [6, 2]
다음 카드 6을 맨 아래로 옮긴다.
현재 카드 상태: [2, 6]
여섯 번째 처리: 현재 카드 상태: [2, 6]
제일 위에 있는 카드 2를 버린다.
남은 카드: [6]

마지막으로 남은 카드 6을 반환한다.

따라서, 7장의 카드가 있을 때 마지막으로 남는 카드는 6번 카드다.

하지만, 이 코드는 백준의 채점 기준으로 틀린 코드라고 나온다. 😶‍🌫️
알아 본 결과 백준은 input으로 임의의 값을 받아야 하고
프로그래머스는 solution 함수 안에서 끝내는게 정석이라고 한다.

함수를 사용하지 않고 다시 짠 코드

from collections import deque

n = int(input())
cards = deque([i for i in range(1, n+1)])
while len(cards) > 1:
    cards.popleft()
    front_card = (cards.popleft())
    # front_card 변수에 현재 상단에 있는 카드를 저장 / * 2
    
print(cards[0])