백준 11003번 최솟값 찾기

< 백준 11003번 최솟값 찾기 - 마포 코딩박 >

사용한 알고리즘: priority_queue


 N 개의 수들과 수 L 이 주어집니다. 각 i번째 입력마다 i-L+1 ~ i 수 중 가장 작은 수를 출력하는 문제입니다. pq를 사용하여 문제를 해결했습니다.

문제풀이는 다음과 같습니다.
(1) (코드 7~12)
 각 i번째 입력마다 < 숫자, 위치 > 의 pair 로 i번째 수와 i 를 저장해주었습니다.
 이를 pq 에 넣어, 숫자가 작은 순으로 정렬했습니다.

(2) (코드 17~27)
 입력이 들어올때마다 만들어 놓은 pq 에 넣습니다.
 pq의 위부터 보며 i-L+1 이전 위치의 pair 은 지워줍니다.
 pq 에 남은 수중 맨 위수가 범위 i-L+1 ~ i 에 들어오는 가장 작은 수입니다.

	#include <bits/stdc++.h>
	using namespace std;
	// < 숫자 , 위치 >
	typedef pair<int, int> pii;
	int N, L;
	struct cmp{
	bool operator()(const pii &t, const pii &u){
	return t.first > u.first;
	}
	};
	priority_queue<pii, vector<pii>, cmp> pq;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> L;
	for (int i = 0; i < N; ++i){
	int a;
	cin >> a;
	// pq 에 들어오는 수 다 때려넣기
	pq.push(pii(a,i));
	// i-L+1 이전의 수는 pq 에서 제거
	int start = i-L+1;
	while(start>=0 && pq.top().second < start) pq.pop();
	// pq 에 남은 수 중 제일 작은 수가 맨 위에 있을꺼임
	cout << pq.top().first << ' ';
	}
	return 0;
	}

view raw BOJ 11003.cpp hosted with ❤ by GitHub