[Baekjoon/백준][11003][C/C++] 최솟값 찾기

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

자료구조, 우선순위 큐, 덱 문제.

1. 문제

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

11003번: 최솟값 찾기

[문제]

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

[입력]

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

[출력]

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

[예제 입력 1]

12 3
1 5 2 3 6 2 3 7 3 5 2 6

[예제 출력 1]

1 1 1 2 2 2 2 2 3 3 2 2

반응형

2. 풀이

이 문제를 풀기 위해서는

1. Sliding Window 알고리즘.

2. Priority_queue를 임의의 순서대로 정렬할 수 있게 하는 방법.

위 두가지에 대해 알고 있어야 한다.

 

'Di = Ai-L+1 ~ Ai' 라는 말은 결국, 길이가 L인 부분 구간에서 찾은 최솟값을 구하라는 말인데, 이는 다음 그림과 같다.

[Baekjoon/백준][11003][C/C++] 최솟값 찾기

[Navie한 풀이] : 위 내용을 Naive 하게 풀게 되면, $O(NL)$의 시간복잡도가 소요된다. 이는 시간초과가 발생하는 원인이 된다.

컨테이너 삽입 : $O(1)$

최솟값 찾기 : $O(L)$

컨테이너 삭제 : $O(1)$

 

[Priority Queue를 이용한 풀이] : $O(NlogL)$

컨테이너 삽입 : $O(logL)$

최솟값 찾기 : $O(1)$

컨테이너 삭제 : $O(logL)$

 

핵심 로직은 다음과 같다.

cmp를 통해 val 값이 가장 작은 원소를 priority_queue의 최상단에 위치하도록 설정한다.

(val 값이 동일하다면, 가장 늦게 들어온 원소, 즉 idx값이 가장 작은 원소가 최상단에 위치한다.)

이후, 최솟값의 idx를 확인하는데, 최솟값의 idx가 sliding window에 포함되지 않는 범위라면 (idx - L 보다 그 값이 작거나 같다면) priority_queue에서 제거한다. while문을 통해 해당 과정을 수행하면 결국 priority_queue의 최상단에는 sliding window의 범위에 포함되는 원소 중 최솟값이 위치하게 된다.

3. 코드

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

struct cmp { //priority_queue를 위한 비교 함수.
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
		if (a.second != b.second)
			return a.second > b.second; //val 기준 오름차순 정렬.
		else
			return a.first > b.first; //idx 기준 오름차순 정렬.
	}
};

int main(int argc, char* argv[]) {
	/* Faster */
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	/* Init */
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq; //idx, val
	
	/* Input */
	int n, l; cin >> n >> l;
	for (int idx = 0; idx < n; idx++) {
		/* Input */
		int val; cin >> val;
		
		/* Logic */
		pq.push(make_pair(idx, val));

		while (pq.top().first <= idx - l)
			pq.pop();

		/* Output */
		cout << pq.top().second << ' ';
	}

	/* Return */
	return 0;
}

/* 
Sliding Window 알고리즘.

Priority Queue 이용.

[naive 풀이]
컨테이너 삽입 : O(1)
최솟값 찾기 : O(L)
컨테이너 삭제 : O(1)

[priority_queue 이용 풀이]
컨테이너 삽입 : O(logL)
최솟값 찾기 : O(1)
컨테이너 삭제 : O(logL)
*/