백준 17298번 오큰수

문제 링크 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

풀이

스택을 이용하는 문제입니다!

우선 stack을 만든 후, 수열 A에 대해서 push를 계속 해줍니다.

단, stack.top() 보다 큰 수가 나왔을 경우 top 원소의 오큰수는 반드시 그 큰 수가 됩니다.

바로 오른쪽에 있는 수이기 때문이죠.

그렇게 오큰수가 정해진 원소는 pop해주고, 또 다시 비교를 반복해 top 원소가 그 수보다 클 때 까지 반복하고, 그 수를 push 합니다. (stack의 원소들이 내림차순이기 때문에 pop을 해도 다음 top의 오큰수는 그 수가 된다)

이 과정을 반복하면 오큰수가 있는 원소들을 모두 구할 수 있고, 과정이 끝나고 stack에 남은 원소들은 반드시 내림차순으로 존재하기 때문에 -1을 대입해주면 됩니다.

간단하지만, 이 과정으로 stack에 내림차순의 수들만 남는다는 걸 반드시 알아야 풀 수 있습니다!

소스 코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int a[1000001];
 
int main()
{
    int n; scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    vector<int> v(n);
    stack<int> s;
    s.push(0);
    for (int i = 1; i < n; i++) {
        if (s.empty()) { //초기 값
            s.push(i);
        }
        while (!s.empty() && a[s.top()] < a[i]) { //오큰수 발견 시
            v[s.top()] = a[i];
            s.pop(); //짝을 찾았으므로 pop
        }
        s.push(i); //현재 idx를 push
    }
    while (!s.empty()) { //짝을 찾지 못한 아이들
        v[s.top()] = -1;
        s.pop();
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~