[백준][C++] 11003: 최솟값 찾기

문제 링크: https://www.acmicpc.net/problem/11003

 

딱봐도 뭔가 슬라이딩 윈도우 같습니다. 근데 N, L 범위가 크기 때문에 구현 방법을 좀 생각해봐야 합니다.

큐, 링크드리스트, 벡터를 쓴다? 윈도우가 한 칸 움직일 때마다 배열 전체를 뒤져봐야 합니다. 큐는 아시겠지만 iterator도 없습니다

힙을 쓴다? min값을 O(1)에 찾을 수 있는건 좋습니다. 그런데 std::priority_queue에는 top에만 접근할 수 있고 다른 값에 접근을 못해 힙에서 원하는 값을 뺄 수 없습니다.

 

Fig 1. 예시

풀이 중 하나는 덱(std::deque)을 사용하는 겁니다.

덱 내부가 인덱스, 값 모두 오름차순으로 정렬되도록 유지하고, 윈도우 크기가 L일 때 한 칸 움직이면 i-L번째 원소를 뺍니다.

인덱스, 값 모두 오름차순으로 정렬하는 방법은 간단합니다. 덱에 원소를 뒤에 넣을 때, 그 원소보다 큰 원소가 있으면 빼버리는 겁니다.

 

예를 들어 Fig 1.의 Iteration 3을 보면 덱에 {1, 5}가 들어가 있고, 2를 넣어야 하는데 덱 맨 뒤에 5가 있으니 5를 뺍니다. 그러면 덱이 {1}이 되는데 1은 2보다 작으니 그냥 넣으면 덱이 {1, 2}가 됩니다.

그 다음 Iteration 4를 보면 먼저 0번째 원소인 1을 덱에서 제거합니다. 여기서 1이 0번째 원소라는걸 알기 위해서는 덱에 값과 인덱스를 함께 넣어야 하겠죠. 3을 덱에 넣는 과정은 Iteration 3과 동일합니다

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int N, L;
	cin >> N >> L;

	vector<int> arr(N);
	for (auto& c : arr)
		cin >> c;

	deque<pair<int, int>> dq;	// (value, idx), 오름차순
	for (int i = 0; i < N; ++i) {
		if (!dq.empty() && dq.front().second <= i - L)
			dq.pop_front();

		// arr[i]가 가장 큰 값이 되도록 만듦
		while (!dq.empty() && dq.back().first > arr[i])
			dq.pop_back();

		dq.emplace_back(arr[i], i);
		cout << dq.front().first << ' ';
	}
	
	return 0;
}

이렇게 푸니 대충 1.4초정도 걸립니다. 입출력에 시간이 많이 들어가나봅니다.