백준 최솟값 찾기(11003) C++ 풀이

알고리즘 분류

자료 구조

우선순위 큐

덱

문제 해결 아이디어

항상 deque의 front의 최솟값이 있도록 하고, 이렇게 하기 위해서 deque의 back보다 더 작은 수가 
들어오면 pop_back()을 반복하여 back()이 현재 들어오는 숫자보다 큰 경우가 없도록 합니다.
또, 구한 i - L + 1이 현재 front()의 idx(deque의 들어온 숫자)랑 같다면 pop_front()를 하여 최솟값을
갱신시킵니다.

코드

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


struct num
{
public:
	int val;
	int idx;
};

deque<num> d;
int n, l;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> l;


	int range;
	int num;
	for (int i = 1; i <= n; i++)
	{
		cin >> num;

		range = i - l + 1;

		while (!d.empty())
		{
			if (d.back().val > num)
				d.pop_back();
			else
				break;
		}

		d.push_back({ num,i });

		cout << d.front().val << ' ';

		if (range == d.front().idx)
			d.pop_front();
	}
}

후기

문제 해결 아이디어는 빨리 생각했지만,  계속 시간 초과가 나서 애를 먹었다. 계속 시간 초과를 줄이는 방법을
생각하다가 '혹시 입출력이 많으니 cin, cout을 빠르게 해야하는 건가?'라는 생각이 들어 cin, cout을 빠르게 하니
해결이 되었다.. 성공했다는 창을 보니 처음에 당황스러웠지만, 의구심이 들었다. '플레티넘 문제 5가 이렇게
쉬울리가 없잖아.. cin, cout을 안 빠르게 해도 푸는 방법이 있겠지..'라는 생각이 들어 한창 고민을 했지만..

결국 나는 생각하지 못했다. 결국 다른 사람 풀이를 찾아봤는데 이런.. 모두 cin, cout을 빠르게 하여 문제를
해결하였다.. 앞으로 입출력이 많은 문제는 난이도 따지지 말고 cin, cout 속도를 고려하고 작성해야겠다..