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

[문제]

코딩테스트 연습 - 뒤에 있는 큰 수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

stack을 이용해서 생각보다 간단하게 풀이가 가능하다.

stack을 이용해서 0번 인덱스부터 접근을 하면서 stack에 저장되어 있는 값보다 작은값이라면 stack에 위에 저장을 해주고 만약, stack에 해당 값보다 작은값이 있다면 작은 값들을 계속해서 빼준뒤에 해당값을 넣어주자.

또한 해당 방식을 사용하면서 pair를 사용해서 pair<값, 위치> 를 이용해 answer 배열에 더 큰값을 위치를 이용해 바로 접근을 해서 저장해주자.

[회고]

stack을 이용해서 풀었다는 힌트를 얻고 시작했던 문제라서 어렵지 않게 풀 수가 있었다.

만일, stack 문제인지 몰랐다면 시간초과로 고생을 했을듯.

[코드]

#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(),-1);
    stack<pair<int, int> > nums;
    nums.push(make_pair(numbers[0],0));
    
    for(int i = 1;i<numbers.size();i++){
        while(nums.size() > 0 && nums.top().first < numbers[i]){
            answer[nums.top().second] = numbers[i];
            nums.pop();            
        }
        nums.push(make_pair(numbers[i],i));
    }
    
    return answer;
}