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

 이 문제는 스택을 이용해서 푸는 문제이다. 처음에는 덱을 이용해서 풀었는데 테스트 22번에서 시간 초과가 났다. 아무리 해도 정답이 나오지 않아 검색을 했고, 스택을 이용해서 훨씬 간단하게 풀 수 있었다. 일단 입력 배열의 최대 길이가 1,000,000 이므로 무조건 O(n) 이하의 알고리즘을 구상해야만 한다.

 

 

 덱을 이용했을 때의 수도 코드는 다음과 같다. (시간 초과)

answer[n] = -1
for (i : n - 1 -> 1)
	만약 numbers[i + 1] > present
		dp.push_front(numbers[i + 1]);
		answer[i] = numbers[i + 1]
	그렇지 않다면
		dp 덱 순회하여 present보다 큰 값 있는지 확인
			만약 없으면 answer[i] = -1
			있으면 answer[i] = 그 값
		dp 덱 다시 그 순서 그대로 복구

 이런 방식으로 풀 때의 문제점은 다시 덱을 복구할 때 한번 더 순회가 일어나기 때문에 시간 초과가 나는 것 같았다. 스택을 이용하면 훨씬 직관적이고 간단하게 문제를 풀 수 있다.

 

 

 스택을 이용한 코드는 다음과 같다.

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

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size());
    
    int n = numbers.size();
    
    stack<int> st;
    
    for (int i = numbers.size() - 1; i >= 0; i--) {
        if (st.empty()) {
            answer[i] = -1;
        }
        else {
            while (true) {
                if (st.empty()) {
                    answer[i] = -1;
                    break;
                }
                
                if (st.top() > numbers[i]) {
                    answer[i] = st.top();
                    break;
                }
                
                st.pop();
            }
        }
        st.push(numbers[i]);
    }
    
    return answer;
}

 

 문제를 풀면서 느끼는 점은 스택을 이용한 풀이에서 위와 같은 형태의 코드가 상당히 많다는 것이다. 덱을 사용했을 때와 달리 이 코드는 스택을 다시 복구하지 않아도 되기 때문에 시간을 훨씬 절약할 수 있다. 스택을 이용하는 풀이는 꼭 머릿속에 기억해놔야겠다는 생각이 들었다.