[프로그래머스] 주식가격 (Lv.2)

---

문제 링크

---

프로그래머스 - 주식가격

문제 설명

---

초 단위로 기록된 주식 가격 배열 prices가 주어진다. 각 시점에서 가격이 떨어지지 않은 기간(초) 을 구해서 배열로 반환하라.

예) prices = [1, 2, 3, 2, 3] → [4, 3, 1, 1, 0]

• 1초 시점 가격 1 → 4초 동안 가격이 떨어지지 않음 (2, 3, 2, 3)
• 3초 시점 가격 3 → 1초 뒤인 4초 시점에 2로 떨어짐 → 1초

내 풀이

---

이중 for문으로 i번째 가격을 기준으로 j=i+1부터 순회한다. 매 초 time을 증가시키고, prices[j]가 prices[i]보다 낮아지면 break로 중단한다. 끝까지 떨어지지 않으면 자연스럽게 루프가 종료되며 남은 초만큼 카운트된다.

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

시간복잡도 분석

---

이중 for문이므로 O(n²).

n = prices 길이 ≤ 100,000이므로 최악의 경우 O(100,000²) = O(10¹⁰) → 이론상 시간초과 위험이 있으나 프로그래머스 채점 기준에서는 통과된다. 스택을 활용하면 O(n)으로 풀 수 있다.

오답노트

---

처음에 if(prices[i] <= prices[j]) time++으로 구현했는데 두 가지 문제가 있었다.

1. 가격이 떨어지는 그 초를 카운트하지 않음 — 떨어지는 순간도 1초로 세야 함
2. 떨어진 이후에도 루프가 계속 돌면서 이후에 오른 구간까지 카운트해버림

수정: 매 초 무조건 time++하고, 가격이 떨어지면 break로 즉시 중단.

후기

---

스택 문제인데 스택을 활용하지 못한 것 같다.

스택으로는 이렇게 풀 수 있을 것 같다.

vector<int> solution(vector<int> prices) {
    int n = prices.size();
    vector<int> answer(n, 0);
    stack<int> s;

    for (int i = 0; i < n; i++) {
        while (!s.empty() && prices[s.top()] > prices[i]) {
            int idx = s.top(); s.pop();
            answer[idx] = i - idx;
        }
        s.push(i);
    }

    while (!s.empty()) {
        int idx = s.top(); s.pop();
        answer[idx] = n - 1 - idx;
    }

    return answer;
}

핑계기는 하지만 소음 때문에 집중을 잘 못한 것 같다. 조금 더 집중하도록 노력해야겠다.

• algorithm
• codingtest
• stack