[BOJ 11003] 최솟값 찾기

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

A. 사용한 알고리즘 및 자료구조

heap을 사용한 priority queue를 사용하였다. i-l+1~i까지 최솟값을 구하면 되기 때문에 일단 들어오는 모든 원소들을 우선순위 큐에 넣어주었다. 구조체를 만들어서 원소 자체의 값과 원소가 언제 들어왔는지 알려주는 변수를 만들었다. 만약 i-l+1의 범위에서 벗어나는 원소가 우선순위 큐의 top에 존재할때 범위 안에 속하면서 가장 작은 값을 가진 원소가 top에 위치해야하기 때문에 while문을 통해 pop을 진행해준다. while 문이 끝난다면 top 원소가 queue에 삽입된 시간이 i-l+1~i의 범위에 속하는 것이 분명하기 때문에 top 원소의 값을 출력해준다.

 

B. 코드

#include<iostream>
#include<queue>

using namespace std;
int n,l;

typedef struct node
{
	int num;
	int when;
}node;

struct cmp {
	bool operator()(node a, node b)
	{
		if (a.num == b.num)
			return a.when < b.when;
		else return a.num > b.num;
	}
};

int main(int argc, char** argv)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> l;

	priority_queue<node,vector<node>,cmp>pq;

	int temp;
	node temp_node;
	int check;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		temp_node.num = temp;
		temp_node.when = i + 1;
		pq.push(temp_node);

		check = i - l + 2;
		if (check <= 0)
			check = 1;
		while (pq.top().when < check)
		{
			pq.pop();
		}
		cout << pq.top().num << " ";
	}
	cout << "\n";
	return 0;
}

C. 후기

SWEA에서 풀고있는 heap문제들을 풀다보니 heap관련 문제에 약한것 같아서 백준에서 찾아서 풀어보았다. 우선순위 큐는 라이브러리 없이 하도 많이 구현해봤기 때문에 이번에는 라이브러리를 사용하였다. 이제 어느정도 heap이 무엇인지, 라이브러리 없이 처음부터 끝까지 구현할 수 있는 자신감이 생긴것 같다.