[백준 11003번] 최솟값 찾기

🔗백준 알고리즘

와,, 내가 플레티넘 문제를 푸는 날이 오는구나 싶었고 처음으로 높다고 생각하는 난이도를 스스로 해결해서 굉장히 기뻣다 !! 물론 플레티넘 문제 중에서도 쉬운 편인 문제 같기는 하지만 풀었다는 것에 의의를 두기로 ,,,,

문제 분석

이 문제는 A[i-L+1 ~ i] 사이의 최솟값 D를 출력하는 문제이다.

이때 i-L+1 ~ i의 크기는 항상 L로 일정하므로 미리 준비된 배열의 0보다 크고 배열의 크기보다 작은 L사이즈의 배열의 최솟값을 출력하는 문제로 이해해도 된다.

예를 들어

N : 6 | L : 3

A : [ 1, 5, 2, 3, 6, 4 ]

---------------------------------------------------------------------------

[ 1 ]
최솟값 : 1

[ 1, 5 ]
최솟값 : 1

[ 1, 5, 2 ]
최솟값 : 1

[ 5, 2, 3 ]
최솟값 : 2

[ 2, 3, 6 ]
최솟값 : 2

[ 3, 6, 4 ]
최솟값 : 3

---------------------------------------------------------------------------

output
1 1 1 2 2 3

항상 L의 사이즈의 범위 내에서 최솟값을 검색하며 이런식으로 출력이 되게 된다.

발상

문제를 처음 보자마자 일정 배열안에서 최솟값을 찾아야하는 로직이 메인이므로 항상 최솟값이 앞에 오도록 하는 priority_queue를 사용하면 되겠다는 생각을 하였다.

이때 큐에 맨 앞에는 해당 배열에서의 최솟값이 들어가게 된다.

해당 최솟값이 존재할 수 있는 범위는 L 만큼 이므로 최솟값의 인덱스에서 L만큼 지나가게 되면 해당 값은 더이상 최솟값이 될 수 없다.

이러한 발상을 토대로 큐에 배열의 값을 게속 담아주며 만약 현재 큐의 최솟값이 범위를 넘어섰다면 삭제해주는 작업을 해주기로 하였다.

현재 큐의 최솟값이 범위를 넘어섰는지 확인하기 위해서 큐는 해당 최솟값의 인덱스또한 알고 있어야 하기에 인덱스와 값을 담는 구조체를 만들어 큐에 담아주었다.

알고리즘 설계

1. 기본 배열 A에 값을 채워넣는다.
2. A의 첫번 째 값부터 마지막 값까지 for문을 돌며 priority_queue에 채워준다.
   만약 현재 큐의 최솟값의 인덱스가 범위 밖이라면 범위 안에 최솟값을 찾을 때까지 큐의 값을 제거해준다.
3. 현재 큐의 최솟값을 출력한다.

코드

#include<iostream>
#include<queue>

using namespace std;

struct A{
    int index;
    int value;
};

struct ASort{
    bool operator()(A& a, A& b){
        return a.value > b.value;
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    priority_queue<A, vector<A>, ASort> pq;
    vector<int> nums;

    int n, l;
    int num;

    cin >> n >> l;

    for(int i = 0; i < n; i++){
        cin >> num;
        nums.push_back(num);
    }

    for(int i = 0; i < n; i++){
        pq.push({i, nums[i]});
        int pos = pq.top().index;
        while(pos < i - l + 1){
            pq.pop();
            pos = pq.top().index;
        }
        cout << pq.top().value << " ";
    }
}