C++로 풀어보는 슬라이딩 윈도우 최대값 문제

크기가 k인 슬라이딩 윈도우가 배열 nums의 왼쪽에서 오른쪽으로 한 칸씩 이동한다고 가정해 보겠습니다. 이때 우리는 윈도우 안에 있는 k개의 숫자만 볼 수 있으며, 윈도우가 이동할 때마다 각 위치에서 볼 수 있는 숫자들 중 최대값을 찾아야 합니다.

예를 들어 입력이 [1, 3, -1, -3, 5, 3, 6, 8]이고 k가 3이라면, 윈도우는 다음과 같이 이동하며 각 단계의 최대값을 얻게 됩니다.

문제 해결 접근 방법

이 문제를 효율적으로 해결하기 위해 덱(Deque)을 활용한 방법을 사용합니다. 덱에는 배열의 인덱스를 저장하며, 덱의 앞쪽에는 항상 현재 윈도우 내 최대값의 인덱스가 위치하도록 유지합니다. 이렇게 하면 전체 시간 복잡도를 O(n)으로 줄일 수 있습니다. 단계별 과정은 다음과 같습니다.

• 결과를 저장할 배열 ans를 정의합니다.
• 인덱스를 저장할 양방향 큐(덱) dq를 하나 정의합니다.
• nums의 크기가 0이면 빈 배열 ans를 반환합니다.
• i := 0부터 i < k까지 반복하면서:
  • dq가 비어 있지 않고 dq의 마지막 인덱스에 해당하는 값이 nums[i]보다 작으면, 그 요소를 뒤에서 제거합니다.
  • i를 dq의 끝에 삽입합니다.
• i := k부터 i < nums.size()까지 반복하면서:
  • dq의 맨 앞 인덱스에 해당하는 값을 ans에 추가합니다.
  • dq가 비어 있지 않고 dq의 맨 앞 인덱스가 (i - k + 1)보다 작으면, 즉 윈도우 범위를 벗어났다면 앞에서 제거합니다.
  • dq가 비어 있지 않고 dq의 마지막 인덱스에 해당하는 값이 nums[i]보다 작으면, 뒤에서 제거합니다.
  • i를 dq의 끝에 삽입합니다.
• 마지막으로 dq의 맨 앞 인덱스에 해당하는 값을 ans 끝에 추가합니다.
• ans를 반환합니다.

이 방식에서 각 인덱스는 최대 한 번 삽입되고 한 번 제거되므로, 전체 알고리즘의 시간 복잡도는 O(n)입니다.

예시 코드

아래의 C++ 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector <int> ans;
        deque <int> dq;
        if(nums.size()==0)return ans;
        for(int i =0;i<k;i++){
            while(!dq.empty() && nums[dq.back()]<nums[i])dq.pop_back();
            dq.push_back(i);
        }
        for(int i = k;i<nums.size();i++){
            ans.push_back(nums[dq.front()]);
            while(!dq.empty() && dq.front()<(i-k + 1))dq.pop_front();
            while(!dq.empty() && nums[dq.back()]<nums[i])dq.pop_back();
            dq.push_back(i);
        }
        ans.push_back(nums[dq.front()]);
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,3,-1,-3,5,3,6,8};
    print_vector(ob.maxSlidingWindow(v,3));
}

입력

{1,3,-1,-3,5,3,6,8}

출력

[3, 3, 5, 5, 6, 8]