뒤에 있는 큰 수 찾기 / stack

 

https://school.programmers.co.kr/learn/courses/30/lessons/154539

앞에서부터 각 원소에 대해 차례대로 루프를 돌며 자신보다 큰 뒤의 수를 찾게 되면, 최악의 경우 O(n^2)의 시간 복잡도가 발생하게된다.

n 값이 매우 커서 어떻게 접근해야할지 한참을 고민하다가 자신보다 뒤에 큰 수를 구하는 것이기에 뒤에서 부터 탐색하면 어떨지 생각해보게 되었고, 현재 탐색하는 원소 보다 이전에 큰 수가 있었는지 확인하기 위해,  이전에 탐색한 큰 수를 저장할 컨테이너로 stack을 활용해보도록 했다.

✅ 구현 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> numbers) 
{
    int n = numbers.size();
    vector<int> answer(n, -1);
    stack<int> st;

    // 뒤에서부터 순회
    for (int i = n - 1; i >= 0; --i)
    {
        // stack에 현재 탐색하는 원소보다 큰 값만 남기고 전부 삭제
        while (!st.empty() && numbers[i] >= st.top())
        {
            st.pop();
        }

        // 탐색하는 현재 원소보다 뒤 원소가 더 크다면 answer에 stack의 값 추가
        if (!st.empty())
        {
            answer[i] = st.top();
        }

        // 뒤에서부터 모든 원소는 stack에 저장
        st.push(numbers[i]);
    }

    return answer;
}

1️⃣뒤에서 부터 순회하며 각 원소들을 stack에 저장
2️⃣stack이 비어있지 않았을 때, stack의 top 원소가 numbers[i]보다 큰 값을 제외하고 모두 제거
3️⃣numbers[i]보다 stack의 top 원소가 더 크다면, 그 값이 해당 인덱스 자리에서 뒤에 오는 큰 수를 의미
4️⃣이 로직을 numbers의 첫 번째 인덱스까지 반복하면, answer 배열의 각 인덱스 자리에 다음에 오는 큰 수가 저장됨