[Hackerrank] 27. Deque-STL

27. Deque-STL

[ 난이도: Medium | 분야: STL ]

1. 내용 정리

Double ended queue 나 deque(C++ STL에서 나온)는 양 끝단에서 확장하거나 축소할 수 있는 동작 크기를 갖는 시퀀스 컨테이너다. 자주 사용하는 deque의 멤버 함수는 다음과 같다:

Deque 템플릿

std::deque<value_type>

 

선언

deque<int> mydeque;

int 형식의 double ended queue의 deque를 생성한다.

 

크기

int length = mydeque.size();

Deque의 크기를 반환한다.

 

Push

mydeque.push_back(1); // Pushes element at the end
mydeque.push_front(2); // Pushes element at the beginning

 

Pop

mydeque.pop_back(); //Pops element from the end
mydeque.pop_front(); //Pops element from the beginning

 

Empty

mydeque.empty() // Returns a boolean value which tells whether the deque is empty or not

 

2. 과제

주어진 크기가 N인 배열과 정수 K에 대해, 크기가 K인 각 하위 배열의 정수 최댓값을 찾아라.

입력 형식

입력의 첫 줄에는 테스트 케이스들의 수인 T가 있다. 각 테스트 케이스 별, 배열의 크기인 N과 하위 배열의 크기인 K가 있다. 이 이후에는 배열의 요소인 A_i가 공백으로 구분되어 나열되어 있다.

 

제약 사항

T는 1보다 크거나 같고 1000보다 작거나 같다.

N은 1보다 크거나 같고 10,000보다 작거나 같다.

K는 1보다 크거나 같고 N보다 작거나 같다.

A_i는 1보다 크거나 같고 10000보다 작거나 같다. 여기서 A_i는 배열 A의 i번째 요소이다.

 

출력 형식

각 연속된 크기가 K인 하위 배열에 대해, 가장 큰 정수를 출력해라.

 

입력 예시

2
5 2
3 4 6 3 4
7 4
3 4 5 8 1 4 10

 

출력 예시

4 6 6 4
8 8 8 10

 

설명

첫 번째 경우, 연속된 크기가 2인 하위배열은 {3,4}, {4,6}, {6,3} 그리고 {3,4}이다. 4개의 크기가 2인 하위배열의 최댓값은 다음과 같다: 4 6 6 4

두 번째 경우, 연속된 크기가 4인 하위배열은 {3 4 5 8}, {4 5 8 1}, {5 8 1 4} 그리고 {8 1 4 10}이다. 4개의 크기가 4인 하위배열의 최댓값은 다음과 같다: 8 8 8 10

 

문제

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

void printKMax(int arr[], int n, int k){
	//Write your code here.
}

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

정답

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

void printKMax(int arr[], int n, int k){
	//Write your code here.
    deque<int> mydeque;
    
    for (int i = 0; i < n; i++) {
        if(mydeque.empty()) {
            mydeque.push_back(i);
        }
        
        if(mydeque.front() <= (i-k)) {
            mydeque.pop_front();
        }
        
        while (!mydeque.empty() && arr[i] >= arr[mydeque.back()]) {
            mydeque.pop_back();
        }
        
        mydeque.push_back(i);
        
        if (i >= (k-1)) {
            cout << arr[mydeque.front()] << " ";
        }
    }
    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;
}

 

 

 

 

 

 

ⓒ Hackerrank. All Rights Reserved.