[백준] 11003 최솟값 찾기 (C++)

백준 11003 최솟값 찾기 문제
백준 11003 최솟값 찾기 소스코드

📄 문제 설명

Problem

N개의 수 A[1], A[2], ..., A[N]과 L이 주어진다.
D[i]는 A[i-L+1] ~ A[i] 값 중 최솟값일 때, D[i]를 출력하는 프로그램을 작성하시오.
(이때, i ≤ 0 인 A[i]는 무시하고 D를 구해야 한다.)

Input

첫째 줄 : N과 L(1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄 : N개의 수 (-10^9 ≤ Ai ≤ 10^9)

Output

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

Example Input 1

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

Example Output 1

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

📝 문제 해설

이 문제는 i가 [0]~[N-1]일 때 [i-l+1]~[i] 범위안의 최솟값을 출력하는 문제이다.
가장 작은 값이 필요하므로 우선순위 큐(Priority Queue)를 사용해서 문제를 해결하였다.

▶ 우선순위 큐(Priority Queue)

Queue는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out)형태의 자료구조이다.

반면, Priority Queue는 <우선순위가 높은 데이터>가 먼저 나가는 형태의 자료구조로 
내부적으로 힙(Heap)과 유사하게 구현되어 있으며, 우선순위가 가장 높은 값이 top을 유지한다.

priority_queue reference

// 1. Top이 가장 큰 수 (우선순위가 큰 수일 때)
priority_queue<int, vector<int>, less<int>> pq;


// 2. Top이 가장 작은 수(우선순위가 작은 수일 때)
priority_queue<int, vector<int>, greater<int>> pq;


// 3. 우선순위 재정의하여 사용 (Custom 우선순위)
struct compare{
	bool operator()(int a, int b){
		return a < b; // Top이 가장 작은 수
		// return a > b; // Top이 가장 큰 수
	}
};

priority_queue<int, vector<int>, compare> pq;

다시 문제로 돌아와서,

우선순위 큐를 만들어 값을 넣다보면 범위 외 값이 섞이는 경우가 생긴다.
이를 처리할 수 있도록 값(value)과 위치(idx)정보를 저장하고 있는 구조체(Data)를 만든다.

여기서 작은 값이 되지않는 큰 값들은 pop()해줄 필요가 없다는 것이다.
따라서, 가장 작은 값의 위치(pq.top().idx)가 범위 안([i-l+1] ~ [i])에 있는지 확인하고
범위 바깥 값을 pop() 해주고, 가장 작은 값(pq.top().value)을 프린트해주면 된다.

⚠ scanf() / printf() 시간초과 ?

⚠ 평소 데이터 입출력 시에 C표준 입출력 함수 scanf() / printf()를 사용하는데,
해당 문제는 오히려 위의 입출력 사용시에 시간 초과가 난다.

따라서 cin과 cout을 사용해도 입출력 속도를 높일 수 있는 아래 코드 사용.

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

🔹 ios::sync_with_stdio(false);
// true : 동기화 상태가 default

C와 C++ 입출력 방식을 제한없이 섞어 쓸 수 있어 C++ 버퍼(iostream)와 C의 버퍼(stdio)를
모두 사용하고 동기화가 되어 있어 delay가 발생하는데, 위의 코드로 동기화를 끊을 수 있다.
즉 C와 C++의 버퍼가 서로 독립되어 사용하는 버퍼 수가 줄어들고 속도가 향상된다.

🔹 cin.tie(NULL); cout.tie(NULL);
// cin과 cout이 서로 tie가 되어 있는 상태가 default

---------------------------
std::cout << "Enter name:";
std::cin >> name;
---------------------------

✔ tie 
cin, cout이 묶여있으며 다른 스트림에서 입출력 작업을 하기전에 자동으로 flush(콘솔에 표시)
-> "Enter name" 먼저 출력 이후 입력 받음

✔ untie 
입출력 작업 하기 전에 자동 flush(콘솔에 표시)에 신경쓰지 않는다.
버퍼가 가득 차거나 수동적으로 flush 시켜주기 전까지는 출력되지 않는다.
-> 입력 이후 "Enter name"이 출력될 수 있음

⚠ 주의 사항
1. C의 버퍼와 C++버퍼가 별개로 독립되기 때문에 scanf, printf, getchar같은
C의 입출력 함수와 cin, cout을 섞어쓰면 입출력의 순서가 올바르지 않게 나올 수 있다.
2. 멀티 쓰레드 환경에서 예상하지 못한 결과가 도출될 수 있다. (싱글쓰레드 사용)

</> Source Code

<#include <bits/stdc++.h>

using namespace std;

struct Data{
	int idx;
	int value;
};

struct Comp{
	bool operator()(const Data& a, const Data& b){
		return a.value > b.value;
	}
};

int main() {	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
   
	int n, l;
	cin >> n >> l;
	
	priority_queue<Data, vector<Data>, Comp> pq;
	
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		
		pq.push({i, x});
		
		while(pq.top().idx < i - l + 1){
			pq.pop();
		}
		
		cout << pq.top().value << ' ';	
	}
	return 0;
}