[HackerRank] Deque-STL

https://www.hackerrank.com/challenges/deque-stl/problem

Deque-STL | HackerRank

문제 풀이)

 

총 원소의 개수와 한 묶음의 원소의 개수가 주어질 때, 각 묶음에서 가장 큰 수들을 찾아 순서대로 출력해주는 문제이다.

 

Input & Output

 

5 2

3 4 6 3 4

 

5개의 원소 중, 2개씩 묶으므로 {3, 4} {4, 6} {6, 3} {3, 4} 로 총 4개의 묶음이 나오고 각 묶음에서 가장 큰 수를 뽑아내면

 

4, 6, 6, 4 가 된다.

 

단순하게 n개의 원소(출발원소)에 대해서 묶음의 개수만큼 for문을 돌려 최대값을 찾아가는 것은 시간 초과가 난다.

 

따라서 for문이 덜 돌 수 있도록 조정을 해주어야 한다.

 

먼저 가장 단순하게 조정할 수 있는 것은 n개의 원소에 대해서 모두 조사하는 것이 아니라 n - k까지, 즉 마지막 묶음의

 

첫 원소까지만 for문을 돌려주는 것이다.

 

그 다음은 최대값을 찾는 for문을 줄여주는 것이다. 계속 묶음의 개수만큼 for문을 돌리는 것이 아니라, 최대 값을

 

가리키는 인덱스 이전은 무시해주는 것이다.

 

 

아래는 샘플로 주어지는 두 번째 Input이다.

3

4

5

8

1

4

10

첫 번째 묶음에서 가장 큰 수는 '8'이다.

3

4

5

8

그 다음 묶음은 아래와 같다.

4

5

8

1

4와 5는 이미 최대값 8보다 작은 것을 알고 있으므로 더 이상 고려해줄 필요가 없고, 새로들어온 1과 비교해주면 된다.

 

만약 새로 들어온 수와 비교했을 때 최대 값이 바뀌지 않았다면 start를 1 증가시켜준다. 이 의미는 새로 들어온 수

 

또한 최대값보다 작으므로 탐색 범위에서 제외시켜주는 것이다.

 

이러한 과정을 반복하다 만약 최대 값을 가리키는 인덱스가 묶음의 시작 원소보다 작아진다면, 즉 최대 값이 더이상

 

묶음에 포함되지 않는 경우엔 묶음의 첫 번째 원소부터 시작하여 최대 값을 다시 구해준다.

 

역순으로 데이터가 주어질 경우 최악 O(n^2)로 보인다. 사실 데이터들이 모두 역순으로 주어지면 시간 초과가 나오지

 

않을까 싶은데.. 분명 더 효율적인 방법이 있을 거라고 생각한다.

 

< 소스 코드 >

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

void printKMax(int arr[], int n, int k) {
	// deque<int> dq;
	int start = 0;
	int nMaxIndex = 0;

	for (int i = 0; i <= n - k; ++i)
	{
		if (nMaxIndex < i) start = nMaxIndex = i;
		for (int j = start + 1; j < i + k; ++j)
		{
			if (arr[nMaxIndex] < arr[j])
				nMaxIndex = j;
		}
		if (start < nMaxIndex) start = nMaxIndex;
		else start++;

		cout << arr[nMaxIndex] << " ";
	}
	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;
}

< Discussions에서 본 코드 >

void printKMax(int arr[], int n, int k) 
{ 
    std::deque<int> Qi(k); 
    int i; 
    for (i = 0; i < k; ++i) { 
        while ((!Qi.empty()) && arr[i] >= arr[Qi.back()]) 
            Qi.pop_back();
        Qi.push_back(i); 
    } 

    for (; i < n; ++i) { 
        cout << arr[Qi.front()] << " "; 
  
        if ((!Qi.empty()) && Qi.front() <= i - k) 
            Qi.pop_front(); 
  
        while ((!Qi.empty()) && arr[i] >= arr[Qi.back()]) 
            Qi.pop_back();  
        
        Qi.push_back(i); 
    } 
    cout << arr[Qi.front()] << endl;
} 

내 코드는 maxIndex를 잃어버린 시점에서 다시 maxIndex를 찾는 수행이 필요하지만 위의 코드는 deque에서

 

maxIndex가 내림차순으로 정렬되므로, 다시 구해주지 않아도 front가 계속 maxIndex가 된다.