HackerRank C++, STL, Deque-STL

 

아이디어가 떠오르지 않아 애 먹은 문제,

Heap이나 우선순위큐를 사용한다면 간단히 해결 할 수 있을꺼 같지만,

Deque를 활용하는 문제기에 더 어려웠던 거 같다.

 

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

void printKMax(int arr[], int n, int k){
	//Write your code here.    
    deque<int> de;
    
    for(int i = 0 ; i < n ; i++)
    { 
        // init
        if(de.empty())
        {
            de.push_back(i);
        }
        
        // sub-array의 영역을 벗어난 요소 제거(1칸씩 이동이라 반복 필요 없음)
        if(de.front() <= ( i - k))
        {
            de.pop_front();
        }
        
        // 맨 앞에 가장 큰 값을 유지하기위한 코드
        // 내 현재 값보다 작은 값들은 전부 제거
        while( !de.empty() && arr[i] >= arr[de.back()] )
        {
            de.pop_back();
        }
        
        // 내 현재 값 삽입
        de.push_back(i);
        
        // 초기 sub-array의 영역이 보장되지 않은 상태에서 출력을 막기 위한 부분.
        if( i >= (k-1))
        {
            cout << arr[de.front()] << " ";
        }
        //cout << "dede : " <<de.size() << endl;
    }
    cout << endl;
    
    
}

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;
}

https://www.hackerrank.com/challenges/deque-stl/problem?isFullScreen=true