[C++] 뒤에 있는 큰 수 찾기

 

뒤에 있는 큰 수 찾기

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

 

제한사항 

4 ≤ numbers의 길이 ≤ 1,000,000 

1 ≤ numbers[i] ≤ 1,000,000

 

 

입출력 예

[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

 

제한사항을 확인해 보면, 최대 길이가 100만인데 O(n^2)의 시간복잡도를 가지게 된다면 무조건 시간초과가 발생할 것 입니다. 따라서 스택 자료구조를 사용하여 풀이합니다. 입력받은 numbers 배열의 인덱스를 기준으로 인덱스 값을 스택에 삽입하여 풀이합니다.

 

처음 인덱스 0을 스택에 push한 후 다음 인덱스를 확인하며 스택에 담긴 인덱스의 값에 해당하는 numbers배열의 값과 비교하며 반복합니다. 뒤에 큰수가 있을 경우, answer배열에 해당하는 인덱스에 numbers값을 할당합니다. 뒤에 큰 수가 없을 경우, 스택에 해당 인덱스가 남아있게 됩니다. 이후 마지막에 스택에 남아있는 값들의 answer를 -1로 할당해주면 됩니다.

 

 

 

 

풀이

#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size());
    stack<int> s;
    s.push(0);
    for(int i = 1; i < numbers.size(); i++){
        while(!s.empty() && numbers[s.top()] < numbers[i]){
            answer[s.top()] = numbers[i];
            s.pop();
        }
        s.push(i);
    }
    for(int i = 0; i < answer.size(); i++){
        if(answer[i] == 0) answer[i] = -1;
    }
    return answer;
}