💻 주식가격

분류 : Stack, Queue (스택, 큐)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

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

제한 사항

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

해결 방안

각각 가격의 가격이 떨어지지 않은 기간을 구하여 vector로 return 해주면 되는 문제이다.

떨어지지 않는 기간이면 같거나 높으면 pass하고 떨어지면 기록하면 될 것 같다.

💡 문제 풀이

방법 1 )

Stack을 사용하여 만약 Stack의 맨 위 값이 현재 값보다 클 경우 pop

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    stack<pair<int, int>> stock_bucket; // 주식 가격을 담기 위한 stack {주식 가격, push했을 때의 시간}

    answer.assign(prices.size(), 0);    // 랜덤 엑세스를 위한 공간 배정

    for (int i = 0; i < prices.size(); i++) {
        while (stock_bucket.size() != 0 && stock_bucket.top().first > prices[i]) {
            // 주식 stack이 비어있지 않고 가격이 떨어졌을 시 반복됨
            // 정답의 위치에 떨어지지 않은 기간을 기록한다.
            answer[stock_bucket.top().second] = i - stock_bucket.top().second;
            stock_bucket.pop();
        }

        stock_bucket.push({ prices[i], i });
        // 계속 나머지 가격들을 push 해준다.
    }

    while (stock_bucket.size()) {
        // 모든 주가를 추가를 해준 뒤 나머지 stack에 남은 주가를 처리해준다.
        answer[stock_bucket.top().second] = prices.size() - stock_bucket.top().second - 1;
        stock_bucket.pop();
    }

    return answer;
}

/*
정확성  테스트
    테스트 1 〉	통과 (0.03ms, 3.98MB)
    테스트 2 〉	통과 (0.03ms, 3.96MB)
    테스트 3 〉	통과 (0.18ms, 3.96MB)
    테스트 4 〉	통과 (0.23ms, 3.92MB)
    테스트 5 〉	통과 (0.23ms, 3.97MB)
    테스트 6 〉	통과 (0.02ms, 3.96MB)
    테스트 7 〉	통과 (0.15ms, 3.96MB)
    테스트 8 〉	통과 (0.14ms, 3.97MB)
    테스트 9 〉	통과 (0.02ms, 3.96MB)
    테스트 10 〉	통과 (0.24ms, 3.91MB)

효율성  테스트
    테스트 1 〉	통과 (26.33ms, 24.4MB)
    테스트 2 〉	통과 (19.81ms, 19MB)
    테스트 3 〉	통과 (30.11ms, 26.8MB)
    테스트 4 〉	통과 (23.10ms, 21.4MB)
    테스트 5 〉	통과 (15.55ms, 16.2MB)

채점 결과
    정확성: 66.7
    효율성: 33.3
    합계: 100.0 / 100.0
*/

시간 복잡도 : 2n

Stack을 만들어 순서대로 Push를 해준다. 단 Stack의 top 값이 현재 값보다 클 경우, pop을 하여 인덱스 차이를 통하여 가격이 떨어지지 않은 기간을 구한다.