[프로그래머스] 주식가격 :: Python, Java

ConewLog·2024년 10월 9일

Algorithm 🧮

목록 보기

13/18

문제

🔗 [프로그래머스] 주식가격

[문제]

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

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


[입출력 예]

prices | [1, 2, 3, 2, 3]
return | [4, 3, 1, 1, 0]

아이디어 : stack

prices의 최대 길이가 100,000이므로 요소별로 가격이 감소하지 않는 시간을 하나하나 구한다면 O(n^2)으로 시간초과가 발생한다.

Stack을 활용하여 O(n) 시간 내에 풀이할 수 있다.

풀이과정

기본적으로 인덱스를 순회하며, 이 인덱스를 stack에 push/pop하며 진행한다.
스택 꼭대기에 위치한 인덱스를 x, 현재 탐색중인 인덱스를 i라 할 때
prices[x] <= prices[i] 를 만족할 때까지 stack에서 pop을 수행한 뒤, i를 push한다.
- 이때, pop된 인덱스를 poppedIdx라고 한다면, i와 poppedIdx의 차이로 가격 감소가 일어나지 않은 시간을 구할 수 있다.
- 따라서, answer에 해당 값을 저장해주면 된다.
- answer[poppedIdx] = i - poppedIdx
모든 인덱스를 탐색한 뒤 stack에 남아있는 값들에 대해서도 처리해준다.
- 이 값들은 가격이 감소하지 않은 인덱스들이다.
- 해당 인덱스들의 가격 감소가 일어나지 않은 시간은 prices의 전체 길이 - 1 - 인덱스이다.

풀이과정 시각화

현재 순회중인 인덱스: 0
비어있는 스택에 인덱스 0 push
현재 순회중인 인덱스: 1
스택 꼭대기에 있는 인덱스 0에 대해 prices[0] <= prices[1]이므로 스택에 인덱스 1 push
현재 순회중인 인덱스: 2
스택 꼭대기에 있는 인덱스 1에 대해 prices[1] <= prices[2]이므로 스택에 인덱스 2 push
현재 순회중인 인덱스: 3
스택 꼭대기에 있는 인덱스 2에 대해 prices[2] > prices[3]이므로 스택에서 2를 pop한 뒤, answer에 인덱스 2의 가격이 유지된 시간을 저장
이후, 스택 꼭대기에 있는 인덱스 1에 대해 prices[1] <= prices[3]이므로 스택에 인덱스 3 push
현재 순회중인 인덱스: 4
스택 꼭대기에 있는 인덱스 3에 대해 prices[3] <= prices[4]이므로 스택에 인덱스 4 push
인덱스 순회를 마친 뒤, stack에 남아있는 값들은 끝까지 가격 감소가 일어나지 않은 인덱스들이다. 해당 인덱스들에 대해 몇초간 유지되었는지를 구해서 answer에 저장해준다.

제출 코드

Python

def solution(prices):
    answer = [0] * len(prices)
    
    stack = []
    
    # stack에 인덱스를 추가해간다.
    for i in range(len(prices)):
        
        # top에 위치한 인덱스 가격이, 현재 prices[i]보다 크다면 가격이 감소한다는 뜻
        while stack and prices[stack[-1]] > prices[i]:
            poppedIdx = stack.pop()
            answer[poppedIdx] = i - poppedIdx
        stack.append(i)
    
    # stack에 남은 인덱스 처리
    # 이 인덱스들은 가격이 감소하지 않은 인덱스들이다.
    # 해당 인덱스들의 가격이 유지되는 시간은 ((전체 길이-1) - 인덱스)이다.
    while stack:
        poppedIdx = stack.pop()
        answer[poppedIdx] = len(prices) - 1 - poppedIdx
    return answer

Java

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        Stack<Integer> stack = new Stack<>();
        
        // stack에 인덱스를 추가해간다.
        for (int i = 0; i < prices.length; i++) {
            
            // top에 있는 인덱스의 가격이 현재 들어갈 가격보다 크다면 감소하는 경우이다.
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                int poppedIdx = stack.pop();
                // 가격이 감소하는 시간을 answer에 저장해준다.
                answer[poppedIdx] = i - poppedIdx;
            }
            stack.push(i);
            
        }
        
        // stack에 남아있는 인덱스들을 처리해준다.
        // 이 인덱스들은 가격이 감소하지 않은 인덱스들이다.
        // 해당 인덱스들의 가격이 유지되는 시간은 ((전체 길이-1) - 인덱스)이다.
        while (!stack.isEmpty()) {
            int poppedIdx = stack.pop();
            answer[poppedIdx] = prices.length - 1 - poppedIdx;
        }
        return answer;
    }
}