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

접근 방법

• numbers의 길이가 최대 1,000,000 이므로 O(NxN)은 너무 오래걸린다.
  • 실제로 수행해보니 시간초과가 났다. (7.4초도 통과인데...)
• 뒷 큰수가 나오기 전까지는 이전의 숫자들이 내림차순 혹은 같은 숫자다
  • 탐색중인 숫자가 바로 전 숫자의 뒷큰수가 될 경우 그 이전의 숫자의 뒷큰수가 될 가능성이 있다

구현

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

using namespace std;


vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    stack<pair<int,int>> s; // 뒷 큰수를 찾지 못한 값들의 index , value
    
    for(int i=0; i<numbers.size(); i++) {
        while(!s.empty()) {
            int idx = s.top().first;
            int value = s.top().second;
            
            // 현재 탐색중인 값이 이전 숫자(들)의 뒷큰수가 아님 -> 다음 체크리스트에 넣어준다.
            if (value >= numbers[i]) {
                break;  
            }
            
            // i번째의 수가 이전에 있던 수(들)의 뒷큰수임을 확인
            answer[idx] = numbers[i];
            s.pop();
        }
        
        s.push({i,numbers[i]});  
    }
    
    
    return answer;
}

후기

• 뒷큰수를 발견하기 전까지 이전의 숫자들은 내림차순이 된다는걸 응용해서 stack에 모아두고 하나씩 비교한다는 발상 자체가 대단하다고 생각했다.
• 난 해봐야 뒤에서 부터 탐색해서 stack에 차곡차곡 넣고 한번에 반환하면 되겠다 했는데 바로 시간초과 컷!