백준 오큰수

문제

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

풀이

• 짝을 짖는 문제는 스택으로 바라보자.!

• 이문제는 임의의 위치에서 오른쪽으로 가다가 임의의 위치보다 더 큰숫자가 발견되면 그 숫자가 '오큰수'가 되는 것이다.

• 여기서 stack을 잘못돌리면 o(n)만에 안된다. stack도 잘 굴려야한다.

• 스택에는 배열의 '위치'를 저장해둔다/ while조건을 보면서 해당 위치의 숫자보다 < '더큰 숫자'가 발견되면 오큰수가 결정되는 순간이다. 그때 결과값을 저장하고, 결정된 위치는 pop을 해준다.

소스

#include <bits/stdc++.h>

using namespace std;

int n;
int arr[1000001];
int ans[1000001];
stack<int> s;
int main() {

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];

    }
    memset(ans, -1, sizeof(ans));

    for (int i = 0; i < n; i++)
    {
        //오큰수가 결정되는 순간 ,
        while (!s.empty() && arr[s.top()] < arr[i])
        {
            ans[s.top()] = arr[i];
            s.pop();
        }
        //s는 배열의 위치만 가지고 있다 
        s.push(i);
    }


    for (int i = 0; i < n; i++)
    {
        cout << ans[i] << " ";
    }
    return 0;
}