[C++/STL] Deque-STL

문제

---

Deque-STL | HackerRank

Deque-STL | HackerRank

배열을 보다 작은 크기의 부분 배열로 나누고, 각 부분 배열에서의 최댓값을 찾아 출력하는 문제입니다.

코드 설명

---

모든 부분 배열마다 방문하여 최댓값을 찾는 것은 비효율적이기 때문에 방문을 최소화해야 합니다.

핵심은 부분 배열의 원소들이 어떻게 바뀌는지 파악해야 합니다.

 

그림을 통해 쉽게 이해해보도록 하겠습니다.

위 그림과 같이 배열이 주어졌고, 부분 배열의 크기는 4 라고 가정합니다.

그러면 첫번째 부분 배열에서의 최댓값은 10 입니다.

다음 부분 배열을 보면 범위가 한 칸씩 움직이는 것을 확인할 수 있습니다.

즉, 부분 배열의 첫 번째 원소와 마지막 원소만 값이 바뀐다는 것입니다.

최댓값인 10은 부분 배열에 그대로 남아있으므로 변동이 없습니다.

따라서 부분 배열마다 최댓값을 찾을 필요가 없고, 새롭게 들어오는 값과 기존 최댓값을 비교하면 됩니다.

위 그림과 같은 경우, 최댓값이었던 원소가 범위에서 이탈하는 경우입니다.

새롭게 들어오는 값이 최댓값보다 크면 다행이지만, 보다 작을 경우 이미 부분 배열의 원소가 아닌 값이 최댓값으로 유지되는 문제가 생깁니다.

따라서 이 경우에는 부분 배열을 방문하여 최댓값을 다시 찾아줍니다.

 

    while (i < k) {                //create first 'subArr' and search maximum integer
        if (arr[i] > max) { max = arr[i]; }
        subArr.push_back(arr[i++]);
    }
    cout << max << " ";

    while (i < n) {                         //move range of 'subArr'
        int head = subArr[0];               //save integer taht will go out of range
        subArr.push_back(arr[i++]);
        subArr.pop_front();

        if (subArr[k-1] > max) { max = subArr[k-1]; }   //update 'max'

        if (head == max) {            //If integer out of range is same to 'max'
            max = subArr[0];            //initialize 'max'
            for (auto j : subArr) {        //re-search maximum integer
                if (j > max) { max = j; }
            }
        }

처음으로 생기는 부분 배열에 대한 최댓값을 찾은 후에 그림으로 설명한 방법을 적용하면 됩니다.

deque 타입의 객체인 subArr 는 부분 배열을 저장하는 변수입니다.

부분 배열의 첫 번째 원소를 미리 저장해둔 후, 다음 부분 배열을 만듭니다.

그 과정에서 새롭게 추가된 원소의 값이 이전 최댓값보다 크다면 갱신하고, 아니라면 최댓값을 유지합니다.

그리고 만약 부분 배열에서 제외된 원소의 값이 최댓값이었다면 새로운 부분 배열에서 최댓값을 다시 찾습니다.

 

전체 코드

---

#include <iostream>
#include <deque> 
using namespace std;

void printKMax(int arr[], int n, int k){
    //Write your code here.
    deque<int> subArr;
    int max = arr[0];
    int i = 0;                    //start point of subarray on 'arr'

    while (i < k) {                //create first 'subArr' and search maximum integer
        if (arr[i] > max) { max = arr[i]; }
        subArr.push_back(arr[i++]);
    }
    cout << max << " ";

    while (i < n) {                         //move range of 'subArr'
        int head = subArr[0];               //save integer taht will go out of range
        subArr.push_back(arr[i++]);
        subArr.pop_front();

        if (subArr[k-1] > max) { max = subArr[k-1]; }   //update 'max'

        if (head == max) {            //If integer out of range is same to 'max'
            max = subArr[0];            //initialize 'max'
            for (auto j : subArr) {        //re-search maximum integer
                if (j > max) { max = j; }
            }
        }
        cout << max << " ";   
    }
    cout << "\n";
}

int main(){

    int t;
    cin >> t;
    while(t>0) {
        int n,k;
        cin >> n >> k;
        int i;
        int arr[n];
        for(i=0;i<n;i++)
              cin >> arr[i];
        printKMax(arr, n, k);
        t--;
      }
      return 0;
}

 

참고

---

• deque | cplusplus.com

deque - C++ Reference