[프로그래머스][C++] 뒤에 있는 큰 수 찾기

뒤에 있는 큰 수 찾기

문제 링크

뒤에 있는 큰 수 찾기

분석

numbers의 길이가 100만 이므로, 2중 반복문으로는 풀 수 없습니다.

분할 상환 분석 알고리즘 문제입니다.

단조 스택(Monotonic Stack)을 활용할 수 있습니다.
단조 스택은 스택(Stack) 자료 구조의 변형 중 하나로, 스택의 원소들이 단조 증가 혹은 단조 감소 상태인 스택입니다.

풀이

#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1); // 정답을 반환할 배열 초기값 -1
    stack<int> s;   // 단조 감소 스택
    
    // numbers를 거꾸로 순회
    for(int i = numbers.size() - 1; i < numbers.size(); --i)
    {
        // 현재 값보다 스택의 top이 값이 작을 경우 제거
        while (!s.empty() && s.top() <= numbers[i])
        {
            s.pop();
        }
        
        // 스택이 비어있지 않다면 현재 값의 다음 큰 수는 스택의 top
        if (!s.empty())
        {
            answer[i] = s.top();
        }
        
        // 현재 숫자를 스택에 저장
        s.push(numbers[i]);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• numbers를 순회하는 반복문 $O(n)$
• 현재 값보다 스택의 top이 값이 작을 경우 제거하는 반복문 일시적으로 $O(n)$

공간 복잡도는 $O(n)$입니다.

• 반환할 값을 저장하는 배열 answer $O(n)$
• 최악의 경우 모든 원소가 스택에 들어갈 수 있으므로 s $O(n)$
• $O(n + n)$

테스트 1 〉 통과 (0.01ms, 4.22MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.27MB)
테스트 4 〉 통과 (0.03ms, 4.23MB)
테스트 5 〉 통과 (0.33ms, 4.21MB)
테스트 6 〉 통과 (2.38ms, 5.65MB)
테스트 7 〉 통과 (3.83ms, 5.49MB)
테스트 8 〉 통과 (15.49ms, 15.4MB)
테스트 9 〉 통과 (17.23ms, 15.3MB)
테스트 10 〉 통과 (37.95ms, 26.8MB)
테스트 11 〉 통과 (30.23ms, 26.9MB)
테스트 12 〉 통과 (67.16ms, 50.6MB)
테스트 13 〉 통과 (67.85ms, 50.8MB)
테스트 14 〉 통과 (222.10ms, 121MB)
테스트 15 〉 통과 (356.11ms, 240MB)
테스트 16 〉 통과 (338.96ms, 240MB)
테스트 17 〉 통과 (408.64ms, 240MB)
테스트 18 〉 통과 (339.43ms, 240MB)
테스트 19 〉 통과 (359.13ms, 240MB)
테스트 20 〉 통과 (341.79ms, 238MB)
테스트 21 〉 통과 (382.93ms, 242MB)
테스트 22 〉 통과 (262.98ms, 191MB)
테스트 23 〉 통과 (399.80ms, 240MB)
테스트 24 〉 통과 (0.05ms, 4.21MB)
테스트 25 〉 통과 (0.03ms, 4.21MB)
테스트 26 〉 통과 (0.03ms, 4.14MB)
테스트 27 〉 통과 (0.02ms, 3.64MB)
테스트 28 〉 통과 (0.02ms, 4.21MB)
테스트 29 〉 통과 (0.04ms, 4.16MB)
테스트 30 〉 통과 (0.02ms, 4.2MB)
테스트 31 〉 통과 (0.01ms, 4.16MB)
테스트 32 〉 통과 (0.01ms, 3.67MB)
테스트 33 〉 통과 (0.01ms, 3.71MB)
테스트 34 〉 통과 (0.01ms, 3.68MB)
테스트 35 〉 통과 (0.01ms, 4.23MB)
테스트 36 〉 통과 (0.02ms, 4.21MB)
테스트 37 〉 통과 (0.01ms, 4.14MB)