[프로그래머스] 주식가격 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

코딩테스트 고득점 Kit > 스택/큐

주식가격 | 문제 바로가기

문제풀이 (2022-01-20 WED 💻)

🤔 사담 + ⭐ 풀이의 핵심?!

스택/큐 유형으로 분류되어 있는 문제라서
스택을 활용해서 풀어보려고 머리를 굴렸는데 잘 떠오르지 않았다
그래서 그냥 그대로 구현하는 느낌으로 이중 for문 써서 돌려봤는데
O(N^2) 복잡도라 걱정했는데.. 다행히 시간초과는 안 떴다 (?)

cf) 진짜 신기하게도 이중 for문 쓴 코드랑 stack 쓴 코드랑 효율성이 비슷하게 나타났다
특별히 떠오르는 방법이 없다면 직관적으로 푸는 것도 나쁜 것만은 아닌듯!

🔽 이중 for문 코드 효율성 테스트 결과

🔽 stack 코드 효율성 테스트 결과

오늘 내 풀이는 너무 직관적이라 설명할 게 딱히 없다
👇 스택으로 푸는 방법이 궁금해서 구글링 후 코드를 수정해보았다

✅ 구글링을 통해 얻은 Tip

prices 배열 값, 즉 주식가격을 스택에 넣어보려고 했었는데
prices 배열 인덱스, 즉 해당 주식가격의 시점(초 단위) 을 스택에 넣는 게 핵심이었다

👉 prices 배열을 돌면서
i) 가격이 떨어지지 않은 경우 스택(timeStack)에 시점을 push하고
ii) 가격이 떨어진 경우 현재 시점(i) - 해당 시점(timeStack.top())의 값을
answer 벡터의 해당 시점 인덱스에 저장해주고 해당 시점을 pop해준다

👉 prices 배열을 다 돌았는데 스택(timeStack)이 비어있지 않은 경우에는
끝까지 가격이 떨어지지 않은 해당 시점들이 있다는 뜻이므로 스택이 빌 때까지
마지막 시점(prices.size() - 1)에서 해당 시점(timeStack.top())을 빼준 값을
answer 벡터의 해당 시점 인덱스에 저장해주고 pop해준다

🔽 이중 for문을 활용한 코드 (C++)

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    int N = prices.size();
    vector<int> answer(N, 0);
    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            answer[i]++;
            if (prices[i] > prices[j]) { break; }
        }
    }
    return answer;
}

🔽 stack을 활용한 코드 (C++)

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

using namespace std;

vector<int> solution(vector<int> prices) {
    int N = prices.size();
    vector<int> answer(N);
    stack<int> timeStack;

    for (int i=0; i<N; i++) {
        while (!timeStack.empty() && prices[i] < prices[timeStack.top()]) { // 가격이 떨어진 경우
            answer[timeStack.top()] = i-timeStack.top(); // 떨어지지 않은 기간 계산 (현재 시점 - 해당 시점)
            timeStack.pop(); // 해당 시점 pop
        }
        timeStack.push(i); // 현재 시점 push
    }

    while(!timeStack.empty()) { // 끝까지 가격이 떨어지지 않은 나머지 경우들 처리
        answer[timeStack.top()] = (N-1) - timeStack.top(); // 떨어지지 않은 기간 계산 (종료 시점 - 해당 시점)
        timeStack.pop(); // 처리 완료된 해당 시점 pop
    }

    return answer;
}