백준 11003번 최솟값 찾기: C언어, Python 풀이

백준 11003 최솟값 찾기 문제의 해설입니다.
슬라이딩 윈도우 크기로 관리되는 덱을 오름차순으로 유지하고, 같은 값을 그룹화하여 각 구간의 최솟값을 시간복잡도 O(1)에 찾는 최적화 방법을 설명합니다.
최종 코드는 C와 파이썬으로 작성되었습니다.

전략

오름차순 덱?

히스토그램 문제 와 거의 완벽히 똑같다.

L = 6 인 상황을 생각해보자.
$A_{i-5}$ 부터 $A_i$ 까지, 6개의 숫자 중 최솟값이 $D_i$가 된다.

이제 가상의 6칸 저장소에 $A_{i-5}$ ~ $A_i$ 까지 숫자를 저장하고 관리한다고 생각해보자.

$A_1$ 부터 $A_6$ 까지 각각 1, 2, 3, 5, 6, 7 이라고 해보자.
우리의 6칸 저장소에도 역시 1, 2, 3, 5, 6, 7이 들어가 있다. $D_6 = 1$이 되겠다.

$A_7 = 4$ 이라고 하자. 1은 이제 범위에 해당되지 않는다. 저장소에서 은퇴시켜주고 대신 4를 넣어준다.
저장소에는 2, 3, 5, 6, 7, 4 가 들어가 있다. 이제 2가 최솟값이 된다.

여기서 잠깐 생각해보자.
앞으로 나올 $A_8$, $A_9$ ...의 값과 상관없이 5, 6, 7은 최솟값이 될 수 없다.
5, 6, 7이 저장소 내 최솟값이 되려면 4가 저장소에 없어야 한다.
하지만 4는 쌩 신입이고, 이들보다 늦게 은퇴한다. 평생 $D_i$가 될 수 없는 운명에 처해졌다.

이참에 이런 무쓸모 숫자들을 저장소에서 제거하자. 권고사직의 시간이다.
저장소를 2, 3, 5, 6, 7, 4 대신 2, 3, 4, 4, 4, 4로 만들어 주자.
이렇게 해도 $D_i$는 변하지 않는다.

대신 새로운 장점이 생겼다. 매번 이런 권고사직을 수행하면 저장소가 오름차순으로 정렬된다.
이제 $D_i$는 항상 저장소의 첫번째 값이다. O(1)으로 찾을 수 있다.

저장소 크기가 가득 찬 경우 왼쪽에서 원소를 제거하고, 새로운 원소를 오른쪽에 추가해줘야 한다.
권고사직은 우측에서 수행된다. 우측에서 현재 값보다 큰 값들을 전부 제거하고 그만큼 현재 값을 채워준다.
양 끝에서 제저가 이루어지기 때문에 저장소는 덱을 통해 구현하기로 한다.

구현 할 때 는 실제 값과 함께 그 값이 몇 번 나왔는지를 같이 저장해주기로 했다.
5, 6, 7을 빼고 4를 넣을 때, 4를 4번 넣는 것이 아닌 {값: 4, 개수: 4}를 넣어준다.

오아시스 재결합문제에서 상용한 방식이다.

C 언어 풀이

#include <stdio.h>

#define MAX_DEQUEUE_SIZE 5000000

// Element grouped with same number value
struct element_g
{
    int number;
    int size;
};

struct element_g dequeue[MAX_DEQUEUE_SIZE];
int head = 0;
int tail = 0;

int elements[MAX_DEQUEUE_SIZE];

int main(void)
{
    int num_elements;
    int window_size;
    scanf("%d %d", &num_elements, &window_size);

    for (int i = 0; i < num_elements; i++)
    {
        scanf("%d", &elements[i]);
    }

    int current_window_size = 0;
    int element_size;
    for (int i = 0; i < num_elements; i++)
    {
        element_size = 1;

        // Pop larger values, since they can be considered as current value
        while (head != tail && dequeue[tail - 1].number >= elements[i])
        {
            element_size += dequeue[tail - 1].size;
            tail--;
        }

        // Push
        dequeue[tail].number = elements[i];
        dequeue[tail].size = element_size;
        tail++;

        current_window_size++;

        // Overwrite elements array with minium value
        elements[i] = dequeue[head].number;

        // if window is full, pop first for next iteration
        if (current_window_size == window_size)
        {
            dequeue[head].size--;
            if (dequeue[head].size == 0)
            {
                head++;
            }
            current_window_size--;
        }
    }

    for (int i = 0; i < num_elements; i++)
    {
        printf("%d ", elements[i]);
    }
}

Python 풀이

어쩌다 글 쓰고 한참 있다가 파이썬으로도 풀게 되어서 추가.

import sys
from collections import deque
from dataclasses import dataclass

@dataclass 
class ValGroup:
    cnt: int
    value: int

if __name__ == '__main__':
    n_numbers, window_size = map(int, sys.stdin.readline().split())
    numbers = map(int, sys.stdin.readline().split())

    dq = deque()
    curr_size = 0

    for number in numbers:
        cnt = 1
        while dq and dq[-1].value >= number:
            cnt += dq.pop().cnt
        dq.append(ValGroup(cnt, number))
        curr_size += 1

        if curr_size > window_size:
            if dq[0].cnt == 1:
                dq.popleft()
            else:
                dq[0] = ValGroup(dq[0].cnt - 1, dq[0].value)
            curr_size -= 1

        sys.stdout.write(str(dq[0].value) + ' ')