[ C++ / 슬라이딩 윈도우 ] 백준 11003 최소값 찾기

📄 문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.
Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.
이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

⌨ 입력

첫째 줄에 N과 L 입력 (1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄에는 N개의 수 Ai 입력 (-109 ≤ Ai ≤ 109)

💻 출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

📌 예제

[ Input ]

12 3
1 5 2 3 6 2 3 7 3 5 2

[ Output ]

1 1 1 2 2 2 2 2 3 3 2 2

---

📝 풀이

핵심

• Ai-L+1 ~ Ai는 슬라이딩 윈도우의 범위(= 크기)
• 계속 옮겨지는 L 만큼의 크기를 가진 슬라이딩 윈도우의 안에서 최소값을 찾아내 주면 됌.
• 슬라이딩 윈도우에 들어오는 값, 나가는 값을 생각하고 풀어보자!

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

typedef pair<int, int> NODE;

int iN = 0;
int iL = 0;

vector<int> vecNumber;
deque<NODE> deqNumber;
vector<int> vecAnswer;

int iStartIndex = 0;
int iEndIndex = 0;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> iN >> iL;

    int iNumber = 0;
    for (int i = 0; i < iN; ++i)
    {
        cin >> iNumber;
        vecNumber.emplace_back(iNumber);
    }

    for (int i = 0; i < iN; ++i)
    {
        while (!deqNumber.empty() && deqNumber.back().second > vecNumber[i])
            deqNumber.pop_back();

        deqNumber.emplace_back(i, vecNumber[i]);

        iStartIndex = i - iL + 1;

        if (iStartIndex > deqNumber.front().first)
            deqNumber.pop_front();

        vecAnswer.emplace_back(deqNumber.front().second);
    }

    for (int i = 0; i < vecAnswer.size(); ++i)
    {
        cout << vecAnswer[i] << ' ';
    }

    return 0;
}

---

༼ つ ◕_◕ ༽つ 여담

😥 환장의 콜라보
처음으로 작성하는 글... 처음으로 풀어보는 백준 플래티넘 문제...

브론즈 ~ 골드 문제만 풀던 나.. 처음으로 플래티넘 문제를 맞닥뜨리고 풀기도 전에 이미 반 포기상태였다.. 아마 구글링으로 풀이 접근 방법을 보지않았더라면 풀지 못했을 것..

(또 백준 입력, 출력문 제대로 확인 안하고 출력 때 띄어쓰기 안했다가 계속 틀려서 1시간 날려먹었다.)

이 글이 누군가에게 도움이 되길 바란다!

내가 이해한걸 다른 사람들이 보기 쉽게 풀어내는 것 또한 어려운 일이란걸 느끼게 되는 시간이었다.. 후..