백준 11003번 최솟값 찾기(c++)

11003번: 최솟값 찾기

문제분석

문제 자체는 매우 간단한 모습을 볼 수 있다.

N개의 수가 주어지고, L이라는 숫자가 주어진다.

이 떄 D(i) = N개의 수에서 i - L + 1번째부터 i번째 사이의 최솟값을 말한다.

원소의 index가 i<0일 떄는 무시한다...

 

주목해야할 점이 단 한 가지 눈에 띈다.

1. 시간복잡도

---

1. 시간 복잡도

- 처음 문제를 접했을 때, 이중 반복문을 통해, 시작점과 끝점을 잡고 사이의 값 중 가장 작은 값을 출력하고자 했다. 코드는 아래와 같다. (이렇다할 알고리즘을 사용하지 않았음)

첫 번쨰 풀이(c++)

아래에 풀이 코드 존재. 현재는 오답코드를 리뷰하는 과정임.

위 풀이를 보면, vec안에 N개의 숫자를 담아두었다. mini는 L개의 숫자에서의 최솟값이고, 이를 계속해서 새롭게 지정해주었다. 결국 시간복잡도는 O(N * L)이 되고 자연스럽게 시간초과를 보게 되었다.(ㅠㅠ)

---

 

문제풀이

슬라이딩 윈도우의 알고리즘을 사용하면 쉽게 풀이가 가능하다. 슬라이딩 윈도우를 알고자 하면 아래 링크를  통해 공부하고 오길 바란다.

[Algorithm] 슬라이딩 윈도우(Sliding Window) 완.전.정.복

우리의 윈도우는 L개의 숫자범위이다. 여기에 deque를 이용해서 문제를 해결할 것이다.

먼저 deque에 들어갈 데이터형은 pair<int, int>로 한다. 이 때, pair의 first는 전체 배열의 index, second는 해당 index의 원소이다. 

중요 포인트는 deque의 가장 앞의 원소를 현재 구간에서의 최솟값을 저장해두었다. 그리고 N개의 숫자 중 하나씩 지정하며, deque의 가장 끝 원소(L의 범위에서 최솟값 후보 중, 가장 큰 원소)를 해당 숫자와 비교했다.

ex)

[ 1 5 2 3 6 2 3 7 3 5 2 6 ]가 주어지고, L이 3인경우이다.

1. 비어있는 deque에는 1이 최솟값이 된다.

deque : [1]

2. 해당 deque의 끝 원소와 현재 index를 비교한다. deque의 끝 원소는 '1', 현재 원소는 '5'이기에 deque의 원소는 지워지지 않는다. 비교가 끝나면 현재 원소를 넣는다.

deque : [1, 5]

3. 2를 반복한다. 하지만 끝 원소'5'에 비해, 현재 원소 '2'가 더 작으므로, '5'는 최솟값의 후보에서 제외되므로 pop한다. 현재 원소 '2'가 자신보다 작은 원소를 만날 때 까지 비교를 반복한다. '5'가 지워지면, 끝 원소는 '1'이 되고 '2'는 이보다 크므로 비교가 끝난다.

deque : [1, 2]

4. 여기가 포인트! 이제 우리의 비교 index는 2, 3, 4 중 비교해야한다. 하지만 현재 최솟값의 index는? 1이다! 즉, 범위에서 벗어난 원소는 비교해서는 안되기에 없애준다. 후에는 위 방식을 반복하면 된다!

deque : [2, 3]

...

C++ 풀이

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, L;
	cin >> N >> L;
	vector<int> vec(N + 1);
	deque<pair<int, int>> window; // 슬라이딩 윈도우
	for (int i = 1; i < N + 1; i++) {
		cin >> vec[i];
	}

	for (int i = 1; i < N + 1; i++) {
		if (window.empty()) {
			window.push_back(make_pair(i, vec[i]));
			cout << window.front().second << ' ';
			continue;
		}// 처음부터 내부가 비어있는 경우는 처음밖에 없음.

		if (window.front().first < i - L + 1) {
			window.pop_front();
		}// 최소값의 index가(deque_front) L의 범위를 초과했다면

		while (true) {
			if (!window.empty() && window.back().second >= vec[i])
				window.pop_back();
			else
				break;
		}
        // 최솟값의 후보군 중 가장 큰 대상이, 현재 바라보는 대상에 비해 작으면

		window.push_back(make_pair(i, vec[i]));
		cout << window.front().second << ' ';
	}
    
	return 0;
}

코드 리뷰는 언제나 환영입니다!