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

윈도우 안에서 최솟값을 찾는 슬라이딩 윈도우 문제이다.

N과 L이 500만까지 들어오기 때문에 윈도우 안에서 for문을 돌려 모든 수를 확인하고 최솟값을 찾으면 시간초과가 발생한다. 윈도우 안에서 효율적으로 최솟값을 찾을 수 있어야 한다.

 

나는 우선순위 큐를 활용해서 최솟값을 효율적으로 찾았다.

 

흐름을 한번 살펴보면

이런 식으로 진행이 된다.

나는 우선순위 큐에 윈도우 안에 있는 값을 넣고 우선순위 큐의 top에 있는 부분을 출력하게 하였다.

top을 출력할 때는 이 top의 있는 값이 윈도우 내부에 있는지 확인하기 위해서 visited[]배열을 활용하였다.

start가 움직이면 visited[start]를 1로 만들어 주었고 top을 확인했는데 만약 방문된 곳이면 pop을 하고 다시 top을 확인하는 형식이다.

 

#include <iostream>
#include <queue>

using namespace std;

priority_queue<pair<int, int>>pq;

int arr[5000001];
int visited[5000001];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N, L = 0;
	cin >> N >> L;

	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}

	int start = 1;
	int end = 1;

	pq.push({ -arr[1],-1 });

	int i = 1;
	while (true)//여기서 부터 Di를 출력함.
	{
		while (true)
		{
			if (visited[-pq.top().second] == 0)//윈도우 내부에 있는 값인지 확인함.
			{
				/*cout << -pq.top().first << " "<< -pq.top().second<<" " <<i<< endl;*/
				cout << -pq.top().first << " ";
				break;
			}
			else//내부에 없으면 pop
			{
				pq.pop();
			}
		}
		i++;
		if (start < i - L + 1)
		{
			visited[start] = 1;//윈도우가 움직임. start는 이제 윈도우의 외부에 있음.
			start++;
		}
		if (end < N)
		{
			end++;
			pq.push({ -arr[end],-end });
		}
		else
		{
			break;
		}

	}

	return 0;
}

내가 처음에 작성한 코드이다. 

 

다른 사람이 작성한 코드를 살펴보니 훨씬 간단하게 문제를 해결할 수 있었다.

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

void Assignment1();
priority_queue<pair<int, int> > Q;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	Assignment1();
	return 0;
}

void Assignment1()
{
	int N = 0;
	int L = 0;
	cin >> N >> L;

	for (int i = 1; i <= N; i++)
	{
		int num = 0;
		cin >> num;
		Q.push(make_pair(-num, i));
		while (i - Q.top().second >= L)//만약 지금 탑에 있는 값의 index와 i의 차이가 L 이상이면 pop()
		{
			Q.pop();
		}
		cout << -Q.top().first << " ";
	}

}

정말 코드가 간단해졌다.

그냥 단순하게 하나를 넣고 최솟값을 확인하고 하나를 넣고 최솟값을 확인하고를 반복하면 되는 것이다.

만약 top의 index와 지금 넣고 있는 위치의 차이가 L이상이면 top의 있는 값은 윈도우의 범위를 초과함.

3을 확인하게 되면 pq에는 1 2 3 5의 값이 들어가 있다. 현재 pq의 top은 1이다.

이 top의 index 또한 1이고 지금 현재 넣고 있는 위치가 4이다.

현재 넣고 있는 위치에서 top의 위치를 빼면 4-1=3이다.

윈도우의 범위를 벗어난다. 그러므로 pop을 하고 다음 top의 값의 index를 확인한 후 출력을 해야 한다.(만약 그다음 top의 index도 윈도우를 벗어나면 또 pop을 해야 함.)

 

우선순위큐가 아닌 deque을 사용해서 문제를 해결해도 된다.