주식가격

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42584

❔ 문제 설명

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

⚠️ 제한사항

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

• prices의 길이는 2 이상 100,000 이하입니다.

---

💡 풀이 (언어 : Java & Python)

스택을 이용해서 풀었다. 문제의 설명이 부족해서 애매한 부분이 있어서 해맸다. 현재가격을 기준으로 1초후 다음 가격이 떨어졌다면 이후에 가격은 상관없이 가격이 떨어지지않은 기간은 1초로 간주하는 것으로 이해해야 문제에서 요구하는 답을 낼 수 있는것 같다. 스택이 비어있거나, 스택의 맨 위의 수가 현재 순서의 수와 비교해더 크지 않으면 스택에 해당 위치 인덱스를 넣어준다. 반대로 더 크면 스택의 인덱스 값을 제거하고 이 과정을 더 큰수가 나오지 않을 때까지 반복한다. 제거한 인덱스 값으로 '해당 시점의 인덱스 - 제거한 인덱스 값'으로 시간차이를 계산해서 정답 배열의 해당 위치에 저장해준다. 반복문이 끝나면 스택에 남아있는 수들로 '종료시점의 시간 - 해당 스택의 인덱스 값'으로 시간 차이를 계산해서 정답 배열에 저장해준다.

Java

class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[prices.length];
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                int idx = stack.pop();
                answer[idx] = i - idx;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            answer[idx] = (prices.length - 1) - idx;
        }
        return answer;
    }
}

큐를 이용한 풀이를 사용했다. 처음에 왼쪽에서 기준이 되는 수를 빼고 나머지 수들을 모두 비교해서 기준보다 작은 수가 발견되면 반복을 중단하고 다음 기준을 뽑는다.

Python

from collections import deque

def solution(prices):
    que = deque(prices)
    answer = []
    while que:
        standard = que.popleft()
        time = 0
        for price in que:
            time += 1
            if price < standard:
                break
        answer.append(time)
    
    return answer