JArchive 프로그래밍 일기

문제

주식가격 프로그래머스 level2

리뷰

이중 for문 으로 해도 풀린다.

자신보다 큰 수가 몇 개인지 개수를 세는 것이다.

코드 1

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;

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

        int cnt = 0;
        for(int j = i+1; j <prices.size(); j++){
            if(prices[i] <= prices[j]) cnt++;
            else{
                cnt++;
                break;
            }
        }
        answer.push_back(cnt); 
    }

    return answer;
}

리뷰

스택/큐 카테고리에 들어가 있으니 스택을 이용한 풀이를 찾아봤다.
스택에 인덱스를 넣는 방법이다.

prices 가 [ 1, 2, 3, 2, 3 ] 으로 주어졌을 때,
값이 계속 오르는 1, 2, 3 구간은 스택에 0 1 2 로 저장된다. 이 순간 스택의 top 은 2 라는 인덱스가 저장되어 있는 것이다.

prices[4] 는 2라는 값을 가진다.
이 때, prices[st.top()] 과 2값을 비교하면, 3 > 2 가 된다.
가격이 전보다 떨어진 것이다.
이 때, st.top()과 현재 인덱스 i 와의 차이로 answer의 값을 정해준다. 그리고 스택에서 pop 해준다.

주식 가격이 전보다 떨어지는 경우 말고는 현재 인덱스가 스택에 푸시되었을 것이다.

인덱스가 0부터 시작 됨을 감안하여 스택이 빌 때까지 꺼낸다.

코드 2

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

vector<int> solution(vector<int> prices) {
    int size = prices.size();
    vector<int> answer(size);
    stack<int> st; // 인덱스를 저장하는 스택 

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

        // 스택이 비어있지 않고, 스택 top 인덱스의 값이 현재값보다 크다면, pop 
        while(!st.empty() && prices[st.top()] > prices[i]){
            // 가격이 이전보다 떨어졌을 떄 처리 
            answer[st.top()] = i-st.top();
            st.pop(); 
        }
        st.push(i); // 현재 인덱스를 푸시 
    }

    // 인덱스는 0으로 시작함을 감안하여 size-1 에서 st.top()을 빼준다
    while(!st.empty()){ 
        answer[st.top()] = size-st.top()-1;
        st.pop();
    }

    return answer;
}