처음에는 이 문제에 대해서 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 내부에 담고자 하는 수들을 오름차순, 혹은 원하면 내림차순 형태로 담아낼 수 있음을 잘 파악하고 그러한 형태의 코드를 잘 활용해보도록 하자. 이 코드의 형태에 익숙해져있지 않은듯 하다.
'알고리즘 > BOJ' 카테고리의 다른 글
BOJ 1012 유기농 배추 || x 좌표와 y 좌표의 꼬임을 매우매우 조심할것. (0) | 2023.09.16 |
---|---|
BOJ 7576 토마토 || 내 풀이와 거기에서 더 좋은 개선사항. (0) | 2023.09.16 |
boj 5430 AC || parser를 어떻게 구현할 것인가가 핵심이다. (0) | 2023.09.09 |
boj 6549 히스토그램에서 가장 큰 직사각형 || 해당 문제에 대해서 색달라 보이게 접근한 풀이법에 대하여. (0) | 2023.09.05 |
boj 3015번 문제에 대한 새로운 풀이를 찾다가 발견한 색다른 방법에 대하여. 이런 형태로 작성하는 것을 이해해보자. (0) | 2023.09.04 |