boj 11003 최솟값 찾기 || deque를 이용한 풀이에 대해서.

처음에는 이 문제에 대해서 priority_queue를 이용한 풀이에 대해서 생각해 보게 되었고, deque를 이용한 풀이는 제대로 생각나지 않았다. deque를 이용한 풀이를 제대로 떠올리지 못하게 된 배경은, deque를 단순하게 int로만 담는것이 아니라 deque<pair<int,int>> dq; 

형태로 pair를 담는 deque에 대한 구현을 떠올리지 못해서이다. 

지속적으로, stack을 이용한 플래티넘급 문제든, 혹은 queue를 이용한 플래티넘급 문제던 자주 접하게 되는 스타일이 단순하게 int 하나를 담는게 아니라 pair<int,int> 를 담을 수 있게 stack, queue, deque를 선언하면서 순서를 부여하는 형태의 문제들이 있고 그 부분에서 pair를 사용하는것을 쉽게 떠올리지 못하고 있는듯한 느낌이 든다. 

 

다음에는 이렇듯 지속적으로 순차적으로 등장하는 수에 대해서 특정한 요건을 만족하는 수들에 대한 값을 출력하는 문제들에 대해서는

stack에서도, queue에서도, deque에서도 

stack<pair<int,int>> S;

queue<pair<int,int>> Q;

deque<pair<int,int>> DQ; 

 

형태처럼 pair를 담는 형태로 선언하고, 담을때 push_back({i,num}); 형태같은 삽입을 떠올려보도록 하자. 

 

#include <bits/stdc++.h>
using namespace std;

int n, m;
deque<pair<int,int>> dq;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for(int i=0; i<n; i++){
        int num;
        cin>>num;
        
        //이렇게 해야 오름차순으로 정렬되어서 가장 앞쪽에 있는걸 매 인덱스마다 
        //출력하면서 원하는 최솟값들을 나타낼 수 있게 만든다. 
        while(!dq.empty() && dq.back().second>=num)
            dq.pop_back();
        
        dq.push_back({i,num});

        if(dq.front().first<=i-m) //갯수를 유지시키기 위한 코드
            dq.pop_front();
        
        cout<<dq.front().second<<' ';
    }
}
//결국 deque를 이용해서 m개를 넘어가버리게 되면 앞쪽에서 빼버리게 하고, 
//deque 내에서 새롭게 받아들이는 num보다 큰 수는 다 뒤로 다 빼버리게 만들어서 
//새로운 num이 deque에 담긴 수중에서 가장 큰 수가 되도록 증가하는 수들을 deque에 
//담게 만든다. 그렇게 해서 가장 작은 수를 매 인덱스마다 front().second 값을 출력해서 
//나타내는 방식으로 구현.

 

그리고 stack에선, 혹은 deque에서나, 

while(!dq.empty() && dq.back().second>=num)
    dq.pop_back();
        
dq.push_back({i,num});

이런 형태의 코드를 통해서 stack이나 deque 내부에 담고자 하는 수들을 오름차순, 혹은 원하면 내림차순 형태로 담아낼 수 있음을 잘 파악하고 그러한 형태의 코드를 잘 활용해보도록 하자. 이 코드의 형태에 익숙해져있지 않은듯 하다. 

 

  Comments,     Trackbacks