[프로그래머스 뒤에 있는 큰 수 찾기] c++ (코드, 풀이, 스택)

문제 링크

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

프로그래머스

 

문제

 

풀이,코드

 

첫풀이는 당연히 무조건 타임아웃이 날거라고 생각했습니다.

 

이게 타임아웃이 안난다면 진짜 그냥 level0이 아닐까 싶은 코드였습니다. 그래도 한번 테스트를 위해 진행해봣습니다.

 

타임아웃 코드

/*

number배열 자신보다 뒤에보다 크면서 가장 가까이 있는 수  -> 뒷큰수

뒷큰수 없음 -> -1

*/

#include <string>

#include <vector>

using namespace std;

vector<int> solution(vector<int> numbers) {

    vector<int> answer;

   

    for(int i = 0; i < numbers.size();i++){

        int j = i + 1;

        while(1){

            if(j == numbers.size()){

                answer.push_back(-1);

                break;

            }

            if(numbers[i] < numbers[j]){

                answer.push_back(numbers[j]);

                break;

            }

            j++;

        }

    }

   

    return answer;

}

역시나 타임아웃.

 

여기서 처음에는 오르는것에 대해서 반복문 안에서 한번에 ++을 연속성 있게 가져가야하나? 

이럴때 문제에서 스택을 쓰라고 있는게 아닐까 생각합니다.

 

 answers벡터에 대해서 numbers.size()만큼 -1로 초기화를 해준다.

 stack에 넣어버린다 -> top에 대해서 만약에 큰값이 나온다? -> stack에 쌓여있는 그것보다 작은값에 대해서 pop을 반복

 

 결국 -1을 안해도 애초에 -1을 초기화 해버렸기 때문에 그냥 가능

 

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

   

    for(int i = 0;i<numbers.size();i++){

        while(!s.empty()){

            int num = s.top().first;

            int idx = s.top().second;

           

            if(num < numbers[i]){

                answer[idx] = numbers[i];

                s.pop();

            }else{

                break;

            }

        }

        s.push(make_pair(numbers[i],i));

    }

   

    return answer;

}