[스택/큐] 주식가격

programmers.co.kr/learn/courses/30/lessons/42584

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

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

---

Sol1) 반복문 + 조건문

#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 pivot = prices[i];
        int j;
        for(j=i+1; j<prices.size(); j++){
            if(pivot > prices[j]){
                answer.push_back(j-i);
                break;
            }
        }
        if(j == prices.size())
            answer.push_back(prices.size()-i-1);
    }
    
    return answer;
}

 

Sol2) 스택

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

using namespace std;

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

알고리즘

1. prices의 인덱스를 저장하게될 스택을 생성한다. (s)
2. 반복문으로 돌면서 prices의 값이 커지면 스택에 넣고
3. prices가 작아지는 지점에서는 answer의 해당 위치에 값(i-s.top())을 저장하고 pop 시킨다. (이렇게 해당위치에 바로 접근하기 위해서 answer 벡터의 크기를 미리 prices의 크기로 할당해 놓는다.)
4. 위 내용은 반복한다. 이전의 값들도 여기서 prices가 작아질 수도 있으니까!
5. 반복문이 다 돈 후에 스택에 남아있는 값들은 s.size()-s.top()-1의 값으로 채우면서 pop시키며 채운다.

* 즉, stack에는 prices의 값이 증가할 때까지 저장하다가 줄어드는 시점에서 pop시키면서 동시에 해당 지점에 해당하는 값을 answer에 저장한다. 그러다 스택에 남아있는 값들은 이후의 값이 모두 커지는 경우일 것이다.

 

 

 

후기)

이 문제는 이중 포문으로 풀기에는 매우 쉬웠지만 스택을 사용하자니 풀이가 잘 생각나지 않았다.

스택을 사용하면 O(n)으로 풀 수 있으니 알아두자.