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

문제

 

풀이

#include <string>
#include <vector>
#include <stack>
using namespace std;

// Stack
// stack을 이용. 저장해놓고 비교하면서 끝나면 pop

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

 

1. stack에는 number의 index를 저장한다. 
2. stack 마지막 인덱스(top)와 number[i]를 비교하여 뒤에 있는 큰 수를 찾게 되면 answer배열의 해당 index 값을 변경한 후, stack에서 pop 하여 비교를 끝낸다. 
3. 반복문을 돌았음에도 stack 남아있는 값들은, 뒤에있는 큰 수가 없기 때문에 -1을 담는다. 

 

 

 

---

 

다른 사람 풀이

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

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    stack<int> stk;

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

    return answer;
}

처음부터  answer배열을 모두 -1로 초기화 해 주었기 때문에 

스택에 남아있는 answer배열의 index들에 -1값을 넣어주는 과정이 필요 없다. 

 

 

 

유사 문제

https://strong-2-min.tistory.com/52

[프로그래머스]스택/큐 - 주식가격

 

 

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=cpp 

프로그래머스