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

프로그래머스

 

💬 문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 각각의 시점으로부터 가격이 떨어지지 않은 기간은 몇 초인지를 계산한다.

 

📌 주의 사항

• prices의 길이는 2 이상 100,000 이하
  • 모든 경우의 수를 확인하는 경우 O(N^2)으로 최악의 경우 약 100억 번의 연산을 하게 되므로 시간 초과 가능성 존재

 

👌 문제 풀이

방법 1) 이중 for문으로 가격이 떨어질 때까지 count

방법 2) 스택 이용해서 가격이 떨어지는 지점을 pop 하고 가격이 끝까지 떨어지지 않는 시점만 스택에 남도록 함

 

💡 스택을 사용한 방법 

1. answer 배열을 각 시점(인덱스)에 따른 최대 값(해당 시점에서 끝까지 가격이 떨어지지 않는 경우)으로 초기화
2. prices 배열을 돌면서 각 시점 별로 확인: i = 0 ~ prices.length
   
   • Stack의 peek 값(이전 시점)의 가격과 현재 기준 시점의 가격을 비교
   • peek(이전 시점) > i(현재 시점): 가격이 떨어졌음
     • `answer[peek] = i - peek` ➡️ 가격이 떨어진 기간을 계산해서 업데이트
     • `Stack에서 pop()` ➡️ peek 값 시점으로부터 가격이 떨어진 시기가 있으므로 Stack에서 pop
   • Stack에 i 저장
3. prices 배열을 다 돌면 Stack에는 가격이 끝까지 감소하지 않는 시점들만 남게 될 것

 

💻 코드

// 풀이 1
import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        // 기준 시점
        for (int i = 0; i < prices.length; i++) {
        	// 이후 시점
            for (int j = i + 1; j < prices.length; j++) {
                answer[i]++;
                // 가격이 떨어졌다면
                if (prices[i] > prices[j]) {
                    break;
                }
            }
        }
        
        return answer;
    }
}

// 풀이 2
import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < prices.length; i++) {
            answer[i] = prices.length - 1 - i; // 최대 값으로 초기화
            
            // Stack에 저장된 이전 시점의 가격들과 비교
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
            	// 이전 시점에 현재 시점보다 높은 가격이 있는 경우
                int prev = stack.pop();
                // 이전 시점의 answer 값 업데이트
                answer[prev] = i - prev;
            }

            stack.push(i);
        }
        
        return answer;
    }
}

 

📈 결과

이중 for문(풀이 1)과 Stack 활용(풀이 2) 결과 비교