<aside> 💬 lv1, 자료 구조, 데큐

데이터 저장 전략

문제 설명

정수 데이터를 처리하는 데큐가 있습니다. 이 데큐는 최대 크기가 정해져 있으며, 새로운 요소가 추가될 때마다 가장 오래된 요소가 제거됩니다. 여러 개의 데이터가 순차적으로 주어질 때, 각 단계에서 데큐의 상태를 반환하는 코드를 작성해주세요.

스케줄링 알고리즘, DB 캐시 전략이 해당 알고리즘과 관련이 있습니다. 특히 LRU 알고리즘은 정리하고 가시길 권합니다.

제한 사항

데큐의 최대 크기는 주어진 정수로 설정됩니다.
주어지는 데이터는 정수의 리스트입니다.
새로운 요소가 추가될 때, 데큐의 크기가 최대 크기를 초과하면 가장 오래된 요소가 제거됩니다.

입출력 예

입력 (최대 크기, 데이터 리스트)	출력 (각 단계의 데큐)
(3, [1, 2, 3, 4, 5])	[[1], [1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]
(2, [7, 5, 9, 1])	[[7], [7, 5], [5, 9], [9, 1]]
(3, [3, 4, 5, 6, 3, 4, 5, 6])	[[3], [3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 3], [6, 3, 4], [3, 4, 5], [4, 5, 6]]

입출력 설명

예를 들어, 첫 번째 입력에서 최대 크기가 3인 데큐에 [1, 2, 3, 4, 5] 순으로 데이터가 주어집니다. 처음에는 [1]만 데큐에 들어갑니다. 이후 [1, 2], [1, 2, 3] 순으로 데이터가 추가됩니다. 데큐에 4가 추가될 때, 최대 크기를 초과하므로 가장 오래된 요소 1이 제거되고 [2, 3, 4]가 됩니다. 마찬가지로 5가 추가될 때는 2가 제거되어 최종적으로 [3, 4, 5]가 남습니다. 각 단계에서 데큐의 상태를 순서대로 반환합니다.

</aside>

😺 풀이 1. 데큐, 최대 길이 고정

from collections import deque **#1 데큐 함수 불러오기**

def solution(data): **#2 함수 정의**
    max_size, nums = data **#3 데이터 분리**
    dq = deque(maxlen=max_size) **#4 데큐의 최대 길이 고정**
    result = [] **#5 단계별 데큐 상태 초기화**

    for num in nums: **#6 단계 진행**
        dq.append(num) **#7 상태 갱신**
        result.append(list(dq)) **#8 현재 단계 상태 추가**

    return result **#9 각 단계의 데큐 반환**

단계별 풀이 전략

데큐 함수 불러오기

from collections import deque를 통해 deque 함수를 불러옵니다.
함수 정의

solution이라는 함수를 정의합니다. 이 함수는 하나의 인자 data를 받습니다. data는 각 단계의 데큐 상태를 반환하기 위한 최대 크기와 데이터 리스트입니다.
데이터 분리

data에서 최대 크기와 데이터 리스트를 max_size, nums로 언패킹합니다.
데큐의 최대 길이 고정

deque(max_len=max_size)를 통해 최대 크기 max_size만큼의 최대 길이 max_len을 가지는 데큐 자료형을 생성합니다. 이렇게 최대 길이가 주어진 최대 크기로 고정된 데큐를 dq에 할당합니다.
단계별 데큐 상태 초기화

단계별 데큐의 상태를 담기 위해 result에 초깃값으로 비어있는 리스트를 할당합니다.
단계 진행

for 문에서 데이터 리스트 nums의 데이터를 순차적으로 num에 할당할 때마다 단계가 진행됩니다.
상태 갱신

먼저 dq.append(num)을 통해 dq에 현재 단계의 데이터 num을 추가하면서 데큐의 상태를 갱신합니다. 이때, dq 의 최대 길이는 max_size입니다.

그러므로 만일 현재 단계에서 상태 갱신 전에 dq의 길이가 이미 max_size에 도달하였다면, 새로운 객체 num이 추가되기 전에 먼저 dq의 왼쪽 끝 데이터 하나가 제거된 후 num이 추가됩니다.

이런 방식으로 dq의 길이를 최대 크기 max_size로 유지합니다.
현재 단계 상태 추가

list(dq)를 통해 현재 단계의 데큐 상태를 리스트로 형변환해줍니다. result.append(list(dq))를 통해 각 단계의 데큐를 보여주는 result에 현재 단계의 데큐 상태 list(dq)를 추가합니다.
각 단계의 데큐 반환

각 단계의 데큐 상태를 담고 있는 리스트 result를 반환함으로써, 각 단계에서 데큐의 상태를 순서대로 반환합니다.

알아둬야 할 개념

deque의 함수의 키워드 인자 maxlen

기본 형태: deque(maxlen=정수형 숫자)

개념: deque 함수에서 키워드 인자 maxlen은 데큐 자료형의 최대 길이를 정의합니다. 즉, 데큐 자료형은 키워드 인자 maxlen을 전달받으면, 최대 길이 maxlen만큼 객체를 갖도록 제한됩니다.

from collections import deque

nums = [1, 2, 3, 4, 5]
dq = deque(maxlen=3)

for num in nums:
    dq.append(num)
    print((dq))

'''   
# 출력 결과
deque([1], maxlen=3)
deque([1, 2], maxlen=3)
deque([1, 2, 3], maxlen=3)
deque([2, 3, 4], maxlen=3)
deque([3, 4, 5], maxlen=3)
'''

풀이 2. 조건 검사

from collections import deque **#1 데큐 함수 불러오기**

def solution(data): **#2 함수 정의**
    maximum, lst = data[0], data[1] **#3 데이터 분리**
    curr = deque() **#4 단계 데큐 초기화** 
    ret = [] **#5 단계별 데큐 상태 초기화**
    for i in lst: **#6 단계 진행**
        if len(curr) >= maximum: **#7 조건 검사**
            curr.popleft() **#8 왼쪽 끝 데이터 제거**
        curr.append(i) **#9 상태 갱신**
        ret.append(list(curr)) **#10 현재 상태 추가**
    return ret **#11 각 단계의 데큐 반환**