프로그래머스 Level2 - 주식가격 C++

코딩테스트 연습 - 주식가격

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

using namespace std;

vector<int> solution(vector<int> prices) {
    int n = prices.size();
    int temp;
    stack<int> s;
    vector<int> answer(n);
    
    for(int i = 0; i < n; i++){
        while(!s.empty() && prices[s.top()] > prices[i]){   // 가격이 떨어진 경우
            // s.top()의 인덱스와 현재 인덱스 i를 비교해야 한다
            int top = s.top();
            s.pop();
            answer[top] = i - top;
        }
        s.push(i);
    }
    while(!s.empty()){
        int top = s.top();
        s.pop();
        answer[top] = n - top - 1;
    }
    
    return answer;
}

---

 오늘도 할짓없이 프로그래머 채용란을 기웃거리다가 취업을 위한 알고리즘은 프로그래머스가 더 좋다고 해서 프로그래머스 코딩테스트 킷인가에서 찾아본 문제입니다. 난이도는 level2로 백준의 골드 4~5정도 되는 것 같습니다. 마침 어제 백준에서 비슷한 문제를 풀어서 나름 쉽게 풀었던 것 같습니다.

백준 6198 옥상 정원 꾸미기 - C++ 스택

 프로그래머스는 처음이라 main이 없어서 검색을 했는데 대충 보니 main없이 진행을 했습니다. 그래서 일단 어제의 내용을 더듬어서 풀이를 해보면

 

 - prices벡터에는 '벡터의 인덱스 == 주가' 로 되어 있습니다.

 - 벡터의 인덱스를 담아둘 스택을 만든 뒤 "스택이 비어있지 않고, 다음 주식(for문의 i)이 이전 주식(s.top())보다 작으면 주식이 내려간것으로 판단, 인덱스의 차이를 뽑아냅니다."

 - 이후 다음 비교를 위해서 스택에 넣어줍니다.

 - 마지막 스택의 값을 비교하기 위해 아래 while문이 있으며 이곳에서 마지막 값들을 뽑아냅니다.

    - -1을 한 이유는 예제의 마지막 값은 다음 비교 대상이 없기 때문입니다.

---

 이후 풀이를 보니 다른 사람들도 비슷하게 풀이를 했습니다. 만일 스택 관련한 문제를 풀어보지 않았다면 적당히 난이도가 있는 좋은 예제 문제가 될 것 같습니다.