17928 (오큰수)

[jihwankim128]

#include <bits/stdc++.h>

using namespace std;

int n;
stack<int> st;
vector<int> arr;

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

    cin >> n;
    for(int i = 0; i<n; i++){
        int num;
        cin >> num;
        arr.push_back(num);
    }
    int idx = arr.size();
    while(idx--){
        int val = arr[idx];
        while(!st.empty() && st.top() <= val) {
            st.pop();   
        }
        if(!st.empty() && st.top() > val) {
            arr[idx] = st.top();
        }
        else arr[idx] = -1;
        st.push(val);

    }
    for(int i = 0;i<arr.size(); i++){
        cout << arr[i] << " ";
    }
    return 0;
}

3가지 질문으로 문제 해결

1. 스택이 비어있는가? yes -> idx가 가르키는 값(val)보다 큰 값이 없음. 수열[idx] = -1
2. 스택의 탑이 val 이하인가? -> 스택의 탑 아래는 더 작은 값이 존재할 수도 있음. -> val 보다 작거나 같은 값이 없을 때 까지 pop 반복
3. 스택의 탑이 val보다 큰가? yes -> 수열[idx] = 스택의 탑

한번의 작업이 끝날 때 마다 현재 값은 스택에 삽입해야함.

[SHyeonL]

# 17298번 - 오큰수
import sys

input = sys.stdin.readline

n = int(input())
s = list(map(int, (input().split())))
stack = []
ans = [0 for i in range(n)]

stack.append(0)
for i in range(1, n):
    if not stack:
        s.append(i)
    while stack and s[stack[-1]] < s[i]:
        ans[stack[-1]] = s[i]
        stack.pop()
    stack.append(i)
while stack:
    ans[stack[-1]] = -1
    stack.pop()
print(*ans)

리스트를 여러개 쓰니 헷갈린다 이름을 잘 정리하자 본인보다 큰 숫자가 나올 때 까지 해당 인덱스를 push, 큰 숫자를 만나면 pop 하면서 정답 리스트에 값 넣기