백준 17298 // 짝짓기는 stack(push[idx]) / 막대그림을그려라

17298번: 오큰수 (acmicpc.net)

17298번: 오큰수

* 행동영역 :

짝짓기는 stack

stack에 인덱스를 저장하라.

 

ret [0,1,2] 에 모두 7로짝짓기

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;
}