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

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

프로그래머스

 

문제 요약) 주어진 배열 numbers에서 numbers[i] < numbers[i + k] 의 값을 찾아 result[i] = numbers[i + k] 를 리턴하는 문제.

 

[풀이]

• 배열의 크기가 1 <= N <= 1,000,000 이므로 O(N), O(NlogN) 을 고려해야 함.
• 자료구조 문제로 stack 을 활용하여 각 값들을 비교할 수 있다.
  • numbers[i] < numbers[i + 1] 인 경우 즉각적으로 stack 에서 pop 되므로, {1, 3, 2, 4 ... (top)}  와 같이 쌓이지 않도록 관리만 한다면 쉽게 해결된다.
  • 더 큰 값이 없는 경우 -1 을 answer 에 담아야 하므로, answer 의 초기 값을 모두 -1 로 설정
  • stack 으로 관리하면 current index 가 어디인지 알 수 없는데, 현재의 index 와, stack 에서 pop 된 개수를 기반으로 distance 를 구해서 answer 배열에 넣을 수도 있지만 본인은 pair 로 number 값과 index 를 둘 다 관리하도록 처리함.

#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;

    s.push({ numbers[0], 0 });
    for (int i = 1; i < numbers.size(); i++) {
        while (!s.empty() && s.top().first < numbers[i]) {
            answer[s.top().second] = numbers[i];
            s.pop();
        }

        s.push({ numbers[i], i });
    }

    return answer;
}