[스택/큐] 주식가격

문제)

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

 

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

 

 

 

접근)

스택 큐로 풀어보려했는데 도저히 방법이 생각나지 않아서 스택을 쓰지 않고 이중 for문으로 풀었다. 

i번째 원소와 그 이후의 원소들의 값을 비교하면서 가격이 떨어졌을 경우에는 n을 1 증가시킨 후 반복문을 빠져나와 n 값을 answer에 넣는다. 가격이 떨어지지 않은 경우에는 n을 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 n=0;
        for(int j=i+1;j<prices.size();j++){
            if(prices[i]>prices[j]){ //가격이 떨어졌을 경우
                n++;
                break;
            }else{
                n++;
            }
        }
        answer.push_back(n);
    }
    return answer;
}

 

 

 

추가)

스택을 이용한 다른 사람의 풀이이다. 스택에 원소의 값이 아닌 원소의 인덱스 값을 넣어준다. 

i는 시간을 의미하고 prices[i]와 prices[s.top()]을 비교해서 후자가 더 큰 경우는 가격이 떨어진 경우이다. i는 현재 시간을 의미, s.top()은 당시 시간을 의미한다.

 

- 가격이 떨어진 경우

answer[s.top()]에 i-s.top() (현재 시간 - 당시 시간)을 넣어준다. 그리고 pop을 시키고 스택에 i를 넣어준다.  

 

- 가격이 떨어지지 않은 경우

스택에 i를 넣어준다. 

 

스택이 비어있지 않다면 스택이 empty가 될 때까지 answer[s.top()]에 prices의 사이즈 - s.top() - 1을 넣고 pop시켜준다.

이 의미는 종료시간에서 당시의 시간을 뺀다는 의미이다.

#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    int size = prices.size();
    for(int i=0;i<size;i++){
        while(!s.empty()&&prices[s.top()]>prices[i]){ // 가격이 떨어졌을 때
            answer[s.top()] = i-s.top(); // 현재 시간 - 당시 시간
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty()){
        answer[s.top()] = size-s.top()-1; // 종료 시간 - 당시 시간
        s.pop();
    }
    return answer;
}