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

문제

프로그래머스 스택/큐 - 주식가격 (Level 2)

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

 

---

문제 풀이

접근 방식

초 단위로 기록된 주식 가격 배열이 주어질 때,

매 시점마다 가격이 떨어지지 않은 기간을 구하는 문제이다.

 

이 문제는 이중 for문을 사용하여 기준값보다 더 낮은 가격일 때까지의 기간을 측정하여 문제를 해결하였다.

 

스택을 이용하여 문제를 해결할 수도 있다.

이중 for문을 이용한 방법보다는 더 빨랐으나 큰 차이는 나지 않았다.

(스택을 이용한 풀이도 아래에 작성하였다.)

 

---

풀이 코드 - C++

// 풀이 1 : 이중 for문을 이용한 풀이

#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    int len = prices.size();
    int count = 0;
    vector<int> answer(len);
    for(int i = 0; i < len - 1; i++) {
        for(int j = i+1; j < len; j++) {
            answer[i]++;
            if(prices[i] > prices[j])
                break;
        }
    }
    return answer;
}

// 풀이 2 : 스택을 이용한 풀이

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    int len = prices.size();
    for(int i = 0; i < len; i++){
        // 현재 시점의 주식의 가격이 스택의 top에 저장된 시점의 가격보다 낮은 경우
        while(!s.empty() && prices[s.top()] > prices[i]){
            answer[s.top()] = i - s.top();
            s.pop();
        }
        
        // s에는 현재 시점을 저장
        s.push(i);
    }
    
    // 가격이 떨어지지 않은 시점
    while(!s.empty()){
        answer[s.top()] = len - s.top() - 1;
        s.pop();
    }
    
    return answer;
}

실행 결과

풀이 1 실행 결과 : 통과 (100.0)

풀이 2 실행 결과 : 통과 (100.0)