[백준 11003] 최솟값 찾기

문제 링크 => 11003번: 최솟값 찾기 (acmicpc.net)

11003번: 최솟값 찾기

---

우선순위 큐를 이용하는 문제이다. (덱을 활용해도 풀리는 문제)

 

앞과 뒷부분을 가르키도록 하는 변수 front, end를 선언하였다.

 

그리고 priority_queue<pair<int, int>> pq 를 선언하여 첫번째에 배열값, 두번째에 인덱스값을 push하고 오름차순으로 정렬하도록 구현하였다.

 

front ~ end 범위 내에 인덱스가 존재하는 경우 => 가장 작은 값이므로 출력한다.

 

front ~ end 범위 내에 인덱스가 존재하지 않는 경우 => 범위 내에 존재하는 인덱스를 발견하기 위해 pop을 반복한다.

 

근데 우선순위 큐로 푼다면 메모리를 상당히 잡아먹는다는 단점이 있다. 그래서 덱으로도 풀어보면 좋을듯 하다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

long long arr[5000001];

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

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

	priority_queue<pair<int, long long>> pq;
	int front = 2 - l, end = 1;
	while (end <= n) {
		pq.push({ -arr[end],-end });

		while (1) {
			long long x = -pq.top().first;
			int  index = -pq.top().second;
			if (index >= front && index <= end) {
				cout << x << " ";
				break;
			}
			else pq.pop();
		}

		front++;
		end++;
	}

	return 0;
}