[C++/STL] Deque-STL

문제

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