백준 - 최솟값 찾기(11003)

 

 

다음과 같은 예시가 있다고 가정하면

L=3

 

 

1  5  2  3  6  2  3  7  3  5  2  6

idx = 0     1

idx = 1     1  5

idx = 2     1  5  2

idx = 3     5  2  3

idx = 4     2  3  6

idx = 5     3  6  2

idx = 6     6  2  3

idx = 7     2  3  7

idx = 8     3  7  3

idx = 9     7  3  5

idx = 10   3  5  2

idx = 11   5  2  6

 

각 구간마다 최솟값을 출력하는 게 목표이다.

 

 

 

실패한 첫번째 시도

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int sub_main()
{
	int n, l;
	cin >> n >> l;
	vector<int> data(n, 0);
	for (int i = 0; i < n; i++) cin >> data[i];

	for (int i = 1; i <= n ; i++)
	{
		if (i < l) {
		
			int min_data = *min_element(data.begin(), data.begin() + i);
			cout << min_data << " ";
	
		}
		else {
			int min_data = *min_element(data.begin() + i - l, data.begin() + i);
			cout << min_data << " ";
		}
				  
	}
	return 0;
	
}

 

당연히 시간초과가 났다.

각 구간 반복문으로 돌려 최솟값을 일일이 찾아주는 코드이다.

 

 

 

 

두 번째 시도는 우선순위 큐를 이용했다.

pop을 위해서 인덱스도 같이 넣어주었다.

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int n, l;

	cin >> n >> l;
	vector<int> data(n, 0);
	for (int i = 0; i < n; i++) cin >> data[i];

	for (int i = 0; i < n; i++)
	{

		pq.push({ data[i], i });
		
		while (pq.top().second <= i - l) {
			pq.pop();
		}

		cout << pq.top().first << " ";
	}



}

                                                             

pq의 최솟값을 계속 확인해 주면 되지만

그전에 인덱스에 벗어난 값이면 pop을 해준다.

 

 

 

 

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

입출력 최적화 코드를 넣지 않으면 통과할 수 없다.