[C++/스택/큐] 주식가격

문제 출처

프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42584

 

문제 설명

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

제한사항

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

입출력 예

pricesreturn

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

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

 

이전 문제 풀이

https://think-deeply.tistory.com/8

[스택-큐/C++] 주식가격

 

---

코드 & 문제 풀이

지난번과 동일한 점은 구조체를 사용했다는 것이고, 다른점은 스택 사용의 유무인 것 같다.

이번엔 스택을 사용해 스택의 top에는 스택에서 가장 price가 높은 값이 들어가도록 했다. 만약 다음번 price 값이 현재 stack의 top에 있는 price보다 높으면 현재 index(여기선 time 변수)와 top element의 index 차를 구해 가격이 하락하지 않은 지속시간을 구했다. 

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

using namespace std;

struct stock {
    int price;
    int time;
};

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

 

정확성 테스트

	이전 풀이	새로운 풀이
테스트 1 〉	통과 (0.02ms, 4.33MB)	통과 (0.01ms, 4.27MB)
테스트 2 〉	통과 (0.03ms, 4.25MB)	통과 (0.03ms, 3.78MB)
테스트 3 〉	통과 (0.15ms, 4.28MB)	통과 (0.15ms, 4.32MB)
테스트 4 〉	통과 (0.30ms, 4.21MB)	통과 (0.18ms, 4.33MB)
테스트 5 〉	통과 (0.20ms, 4.33MB)	통과 (0.21ms, 4.33MB)
테스트 6 〉	통과 (0.02ms, 4.2MB)	통과 (0.02ms, 4.32MB)
테스트 7 〉	통과 (0.11ms, 4.27MB)	통과 (0.11ms, 4.33MB)
테스트 8 〉	통과 (0.12ms, 4.27MB)	통과 (0.15ms, 4.32MB)
테스트 9 〉	통과 (0.02ms, 4.32MB)	통과 (0.02ms, 4.33MB)
테스트 10 〉	통과 (0.35ms, 4.33MB)	통과 (0.20ms, 4.32MB)

효율성 테스트

	이전 풀이	새로운 풀이
테스트 1 〉	통과 (27.86ms, 24.3MB)	통과 (24.56ms, 24.2MB)
테스트 2 〉	통과 (18.23ms, 18.9MB)	통과 (18.87ms, 18.8MB)
테스트 3 〉	통과 (29.61ms, 26.7MB)	통과 (29.40ms, 26.7MB)
테스트 4 〉	통과 (22.19ms, 21.3MB)	통과 (21.96ms, 21.2MB)
테스트 5 〉	통과 (14.17ms, 16.2MB)	통과 (14.24ms, 16.2MB)

 

피드백

문제 풀이 알고리즘이 비슷해서 그런지 테스트 시간도 비슷하게 나온다. 

리스트를 한 번 돌면서 O(n)

스택에 들어간 값을 빼내기 위해 O(n) => 따라서, O(n)의 시간복잡도를 가진다.