백준 11003 : 최솟값 찾기

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

11003번: 최솟값 찾기

 

우선순위 큐를 사용하여 해결할 수 있는 문제다.

L개의 원소를 우선순위큐에 넣어넣고 뒤에 것을 push해주고 앞에 것을 pop해주면서 계속 최솟값을 추적해주면 된다.

이 때, pop을 해주기 위한 방법으로 두 가지 방법으로 풀어보았는데, 그 풀이는 아래와 같다.

 

1) 우선순위 큐 2개와 일반 큐 하나를 이용한 풀이

#include <iostream>
#include <queue>

using namespace std;

int n, l;
priority_queue<int> pq;
priority_queue<int> del;
queue<int> q;

void solution() {
	int tmp;

	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		// 우선순위큐와 일반 큐에 삽입
		pq.push(-tmp);
		q.push(-tmp);
		// 큐 사이즈가 l보다 크다면
		if (q.size() > l) {
			// 큐의 제일 앞에 있는 원소를 del이라는 우선순위큐로 이동
			del.push(q.front());
			q.pop();
			// del과 pq의 top이 같은 동안 pop
			while (!del.empty() && del.top() == pq.top()) {
				pq.pop(), del.pop();
			}
		}
		cout << -pq.top() << ' ';
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 86220 kb

시간: 2116 ms

 

2) 인덱스를 함께 저장하여 1개의 우선순위큐로 해결하는 방식

#include <iostream>
#include <queue>

using namespace std;
using pii = pair<int, int>;

int n, l;
priority_queue<pii> pq;

void solution() {
	int tmp;

	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		pq.emplace(-tmp, i);
		while (!pq.empty() && pq.top().second <= i - l) pq.pop();
		cout << -pq.top().first << ' ';
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 100452 kb

시간: 1748 ms

 

시간 차이가 꽤 많이 난다. 2번 풀이가 더 간결하고 가독성도 좋고 성능도 좋다.