[C++] 백준(BOJ) -11003 : 최소값 찾기

21 Nov 2023 in Develop on C++, Algorithm Last modified at: 2024-02-01

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ -11003 : 최소값 찾기(링크)

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

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

알고리즘

1. 우선순위 큐
2. 슬라이딩 윈도우

풀이

1. 시간제한 2.4초를 고려하였을 때 이중 for문으로는 시간복잡도 초과가 나온다는 것을 확인
   • N의 최대 범위 500만
2. min heap으로 늘 최소값을 리턴하는 우선순위 큐를 만들어서 구간에 새로운 원소가 추가될 때마다 큐에 넣고 구간에서 범위에 벗어나는 원소들은 큐에서 삭제. 나갈 타이밍을 알기 위해서는 인덱스를 알아야 하니 함께 묶어서 저장 (구조체 활용)
3. 우선순위 큐의 인덱스에 따른 값
   

코드

// BOJ - 11003 : 최소값 찾기
#include<bits/stdc++.h>
using namespace std;

int n, l;

struct A {
	int data;
	int pos;
};

struct cmp // 힙정렬(우선순위큐)를 위한 비교 함수 (A 구조체를 만들어줘서 따로 비교함수 만들어 주는게 필요)
{
	bool operator()(const A& a, const A& b)
	{
		return a.data > b.data; // min Heap이 되게끔, 즉 최소값이 루트에 오게끔
	}
};

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

	cin >> n >> l;
	vector<int> arr(n);
	
	for (int i = 0; i < n; i++) cin >> arr[i];

	priority_queue<A, vector<A>, cmp> pq;
	for (int i = 0; i < n; i++)
	{
		pq.push({ arr[i], i });
		int pos = pq.top().pos;
		while (pos < i - l + 1)
		{
			pq.pop();
			pos = pq.top().pos;
		}
		//cout << pq.top().data << ' ';
		
		priority_queue<A, vector<A>, cmp> tmpQ = pq;
		while (tmpQ.size())
		{
			cout << i << ' ' <<  tmpQ.top().data << "(" << tmpQ.top().pos << ")" << ' ';
			tmpQ.pop();
		}
		cout << '\n';
		
	}

	return 0;
}

평가

• 구조체를 활용해 값과 인덱스를 priority_queue에 함께 저장하는 아이디어
• 우선 순위 큐를 만들기 위한 priority_queue<자료형, vecotr<자료형>, 비교함수> 꼴을 잘 기억하고 비교함수 cmp을 a > b 로 설정해서 min heap을 만드는 방법을 숙지
• 지금 우선순위 큐 내에서 최소 값이 되지만 현재 범위에는 해당되지 않는 것들이 여러개가 될 수 있기 때문에 while문을 이용하여 반복 삭제 해주어야 한다