[코드트리/C++] 차이를 최대로 (Deque/Sliding Window)

문제

https://www.codetree.ai/problems/make-dif-max/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

구상

해당 문제는 특정 window 크기 안의 값들의 최소값, 최댓값을 구해야 하는 문제였다. queue를 이용하여 풀 수도 있지만, deque를 이용한 풀이가 더 효율적이었다.

 

먼저, 원형으로 이루어져있는 값들을 1차원 배열으로 나타내어서 0번부터 k-1번 원소가 마지막에 한번 더 필요했다. 그래서 배열 마지막에 추가로 넣어주었다. 예를 들어 위 사진과 같은 상태에서 k가 4라고 한다면, 배열을 [7, 2, 3, 4, 7, -2, 3, 1] 이 아닌, [7, 2, 3, 4, 7, -2, 3, 1, 7, 2, 3, 4]로 구성했다. 

 

그리고, 최댓값과 최솟값을 각각 구하는데, 각각의 상황에 따른 최소, 최댓값을 minValues, maxValues 배열에 넣고자했다. 그래서, dq라는 인덱스를 추가로 만들어서, 각각의 상황에서의 최솟값/최댓값의 인덱스를 넣도록 했다. 

 

최솟값을 구하는 slidingWindowMin에서의 dq는 front에 최솟값의 인덱스가 있고, back으로 갈 수록 큰 값의 인덱스가 있다. 그리고, front에 과거의 인덱스가 있고, back으로 갈 수록 최근의 인덱스가 있다. 그래서 매번 front쪽에서 window 밖으로 나가는 인덱스를 제거해줘야 한다. 그리고, back쪽에는 비교적 큰 값들이 있으니, 현재의 값보다 크거나 같은 값들은 모두 제거해주었다.(결국 같은 값을 만나면, 최근의 인덱스를 저장하게 된다.) 그리고 나서 현재의 인덱스를 넣었다. dq에는 인덱스가 있으니 오름차순의 수들이 저장되고, 인덱스를 통해 값을 가져온다 해도, 오름차순의 값들이 된다. 

 

최댓값을 구하는 slidingWindowMax에서는 dq는 front에 최댓값 의 인덱스가 있고, back으로 갈 수록 작은 값의 인덱스가  있다. 그리고, front에 과거의 인덱스가  있고, back으로 갈 수록 최근의 인덱스 있다. 위에서와 같이 매번 front 쪽에서 window 밖으로 나가는 인덱스를 제거해주었고, pop_back()을 사용하여 back쪽에서 현재의 값보다 작거나 같은 값들은 모두 제거 후 현재의 인덱스를 넣었다. 결국 dq의 값들 즉, 오름차순으로 인덱스들이 저장되고, 인덱스를 통해 값을 가져온다면, 내림차순의 값들이 된다. 

 

말로는 꽤 복잡한데, 손으로 그려보거나, 코드를 머릿속에서 실행시켜보면 이해하기 쉽다. 그래도 이해하기가 어렵다면, 아래 코드의 주석을 참고하면 좋을 것 같다!

 

풀이 + 코드

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
/*
차이를 최대로 
https://www.codetree.ai/problems/make-dif-max/description
*/
using namespace std;

int n, k;

vector<long long> slidingWindowMin(const vector<long long>& arr, int k) {
    deque<int> dq; // 작은 값의 인덱스
    vector<long long> minValues; // 상황에 따른 가장 작은 값 

    for (int i = 0; i < n + k - 1; ++i) { // k-1번은 그냥 데이터 쌓고, k번째부터 n번 minValues에 값을 넣게 된다. 
        if (!dq.empty() && dq.front() == i - k) { // window 밖으로 나가는 인덱스 제거
            dq.pop_front(); 
        }

        while (!dq.empty() && arr[dq.back()] >= arr[i]) { // 현재값보다 큰 값 제거 => 같은 값이면 가장 최근 값이 저장되는 것!!
            dq.pop_back(); 
        }

        dq.push_back(i); // 현재 인덱스 추가

        if (i >= k - 1) { // window가 처음 k개의 요소를 모두 포함할 때부터, 덱의 앞에 있는 값이 현재 구간의 최소값이므로 이를 저장
            minValues.push_back(arr[dq.front()]);  // arr[i-k+1] ~ arr[i] 중의 최솟값
        }
    }

    return minValues;
}

vector<long long> slidingWindowMax(const vector<long long>& arr, int k) {
    deque<int> dq;
    vector<long long> maxValues;

    for (int i = 0; i < n + k - 1; ++i) {
        if (!dq.empty() && dq.front() == i - k) { // window 밖으로 나가는 인덱스 제거
            dq.pop_front();
        }

        while (!dq.empty() && arr[dq.back()] <= arr[i]) { // 현재값보다 작은 값 제거
            dq.pop_back();
        }

        dq.push_back(i); // 현재 인덱스 추가

        if (i >= k - 1) { // i가 k - 1 ~ n + k - 2 일 때까지 n번 값이 삽입됨. 
            maxValues.push_back(arr[dq.front()]); // arr[i-k+1] ~ arr[i] 중의 최댓값
        }
    }

    return maxValues;
}

int main() {
    // 입력
    cin >> n >> k;
    vector<long long> arr(n);

    // 원형 배열 구성
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    for (int i = 0; i < k - 1; ++i) { // k-1개 추가로 넣기
        arr.push_back(arr[i]);
    }

    // 로직 
    vector<long long> minValues = slidingWindowMin(arr, k);
    vector<long long> maxValues = slidingWindowMax(arr, k);

    // 출력
    for (int i = 0; i < n; ++i) {
        long long diff = maxValues[i] - minValues[i];
        cout << diff << " ";
    }

    return 0;
}