Algorithm/boj
백준 17298 // 짝짓기는 stack(push[idx]) / 막대그림을그려라
Mini_96
2023. 5. 23. 15:56
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
* 행동영역 :
짝짓기는 stack
stack에 인덱스를 저장하라.

a[i] => 입력저장
while(top<입력) ret[idx]=입력, pop
끝나면, push(idx)
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int m, n, a[1000004], ret[1000004];
stack<int> s;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
fill(&ret[0], &ret[1000004], -1);
cin >> n ;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
while (s.size() && a[s.top()] < a[i]) //if가 아니라 while써야함
{
ret[s.top()] = a[i];
s.pop();
}
s.push(i); //idx를 스택에 push하라.
}
for (int i = 0; i < n; ++i)
{
cout << ret[i] << " ";
}
return 0;
}