프로그래머스 뒤에 있는 큰 수 찾기

 

기초적인 문제같은데 시간을 오래 끌었다.

고민을 한시간정도 했다. 요즘 문제를 보면, 갈피가 잡히더라도 그걸 구체화하는게 부족하다.

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

using namespace std;

vector<int> solution(vector<int> numbers) {
    
    stack<pair<int, int>> stk;
    vector<int> answer;

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

    return answer;
}

이래가지고선 아무것도 못 한다.

 

 

새로 알게된 점: vector 초기화를 이렇게 쉽게

    vector<int> answer(numbers.size(), -1);

 

 

---

다시 풀었다.

이런 어려운 사고방식의 구현문제가 분명 중요한데,, 다양한 관점을 보는 것이 필요하다.

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

using namespace std;

// stack, queue 다양한 관점이 필요한 문제였다.
// O(N^2)로는 불가능
// 앞에서부터 살펴보면서, 관심이 없는 것들은 없애버려서 밀어버리면서, 시간복잡도를 줄인다.

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    
    for(int i = 0; i < numbers.size(); i++) {
        answer.push_back(-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;
}