[백준] 11003 - 최솟값 찾기

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

11003번: 최솟값 찾기

 

처음에 이 문제의 시간과 N 범위를 보고 세그먼트 트리를 생각하여 제출했는데 TLE를 받았다.

세그먼트 트리 생성 시간 NlogN + 쿼리시간NlogN 해서 약 2억 2천 번의 연산으로 될 줄 알았는데 아니었고, 입출력 최적화 및 이것저것 해보았는데도 되지 않길래 다른 방법으로 AC를 받았다.

 

문제를 간단하게 표현하자면 이렇다.

[max(1, i - L + 1), i] 구간에서 최솟값

 

당연히 쿼리마다 구간을 탐색하는 N^2의 풀이로는 TLE를 받을 것이고, 이 문제의 풀이 방법에는 2가지가 있다.

 

먼저 덱을 활용한 슬라이딩 윈도우 기법이다.

다음과 같이 덱을 구성하려고 한다.

덱의 첫번째 원소는 찾으려 하는 값이고, 덱은 항상 오름차순으로 정렬되어 있으며, 덱의 크기는 L개 이하이다.

이렇게 덱을 짜놓으면 모든 원소가 덱에서 한 번씩 들어갔다가 나오므로 시간제한 안에 해결이 가능하다.

 

그렇다면 위와같은 덱을 어떻게 구현할 수 있을까?

바로 { number, index } 형태의 pair를 저장하는 덱을 사용하는 것이다.

1. 입력을 받는다.
2. 덱을 정렬 상태로 유지하지 위해 입력받는 수가 dq.back() 보다 작으면 계속 pop() 한다.
   • 이유는, 이 입력 받는 수가 덱에 이미 있는 수보다 작으면, 덱에 이미 있는 수는 절대로 해(최솟값)이 될 수 없기 때문이다.
3. 다음으로 인덱스를 이용해 범위를 벗어난 수들을 앞에서부터 pop() 한다.

#include <iostream>
#include <deque>
using namespace std;

deque <pair<int, int>> dq;

int main(){
	int n, l;
    
    cin >> n >> l;
    for(int i = 1; i <= n; i++) {
    	int num; cin >> num;
        
        while(!dq.empty() && dq.back().first > num) {
        	dq.pop_back();
        }
        while(!dq.empty() && dq.front().second < i - L + 1) {
        	dq.pop_front();
        }
        dq.push_back({ num,i });
        
        cout << dq.front().first << ' ';
    }
}

 

다음으로 우선순위 큐를 이용한 풀이이다.

코드는 정말 단순하다.

간단하게 설명하자면, 덱 코드와 유사하게 { number, index } 형태의 pair를 저장하는 큐를 만들고, 인덱스를 만족하는 조건에서의 top()을 뽑아내는 것이다.

 

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

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int main(){
	int n, l;
    
    cin >> n >> l;
    for(int i = 1; i <= n; i++) {
    	int num; cin >> num;
        
        q.push({ num,i });
        while(q.top().second < i - l + 1) {
        	q.pop();
        }
        
        cout << q.top().first << ' ';
    }
}

 

덱과 힙을 통한 구현 모두 시간 내에 통과하였지만, 힙을 통한 코드가 약 400ms정도 오래 걸렸다.

아무래도 힙을 통한 연산 속도에 의해 영향을 받은 것 같다.