프로그래머스 스택/큐 주식가격

문제 설명

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

---

나의 코드

 

저는 해당 문제를 큐를 사용하여 풀었습니다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int i,k;
    queue<int> q;
    for(i=0;i<prices.size();i++){ //큐에 주식의 가격을 넣음
    	q.push(prices[i]);
	}
    for(i=0;i<prices.size();i++){
    	for(k=1;k<prices.size()-i;k++){
    		if(q.front() > prices[i+k]){ //주식의 가격이 내려간다면
    			answer.push_back(k);
    			q.pop(); //큐에서 해당 주식을 뺌
    			break;
			}
		}
		if(k == (prices.size()-i)){ //만약 끝까지 주식이 내려가지 않는다면
    		answer.push_back(k-1);
    		q.pop();
		}
	}
    
    return answer;
}

---

다른 코드 해석

 

#include <string>
#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]){ 
        //스택에 무언가 있고 스택에 마지막에 들어온 것이 price[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;
}

만약 해당 코드로 [1,2,3,2,3] 을 실행한다면,

 

i = 0일 때, stack이 비어있으니 s.push(0) 시행

i = 1일 때, prices[0] > prices[1]에 해당되지 않으므로 s.push(1) 시행

i = 2일 때, prices[1] > prices[2]에 해당되지 않으므로 s.push(2) 시행

i = 3일 때, prices[2] > prices[3]에 해당되므로 while 안으로 들어감 -> answer[2] = 3-2 실행 -> s.push(3)실행

i = 4일 때, prices[3] > prices[4]에 해당되지 않으므로 s.push(4) 시행 => for문 나옴

 

while문 진입 

answer[4] = 5-4-1 = 0

answer[3] = 5-3-1 = 1

answer[1] = 5-1-1 = 3

answer[0] = 5-0-1 = 4

 

answer = 4,3,1,1,0

 

 

---

2021.11.11 풀이

 

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