[프로그래머스 / Java] Lv.2 주식가격

Question

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

프로그래머스

---

Algorithm

 

💡 Stack 활용한 풀이 방법

1. 배열의 0번째 인덱스부터 순회하며 가격이 떨어지는 지점을 확인한다.
   
   • 각 시점의 가격을 확인하면서, 이전에 저장된 시점들(아직 가격이 떨어지지 않은 시점)과 비교한다.
2. 스택에는 아직 가격이 떨어지지 않은 시점의 인덱스를 저장한다.
   • 예를 들어 prices = [1, 2, 3, 2, 3]라면, 처음에는 0초(가격 1)를 스택에 push한다
   • 스택에는 실제 가격이 아니라 인덱스(index) 가 저장된다.
3. 새로운 가격이 들어올 때마다 스택의 top과 비교한다.
   
   • 현재 가격이 스택의 top 가격보다 크거나 같으면, 가격이 유지 또는 상승한 것이므로 현재 인덱스를 push 한다.
   • 현재 가격이 스택의 top 가격보다 작으면, top에 있던 시점의 가격이 떨어진 것이므로 pop 해서 그 시점의 가격이 유지된 시간을 계산한다.
4. 가격이 떨어졌을 때는 조건이 맞는 동안 계속 pop한다.
5. 모든 시점을 순회한 뒤, 스택에 남은 인덱스를 처리한다.
   • 끝까지 가격이 떨어지지 않은 시점들이므로
   • prices.length - index - 1
   • answer[남은 인덱스] = (마지막 인덱스) - (해당 인덱스) 로 계산한다.

---

Code

 

💡 첫번째 풀이 (이중 for문 -> 시간 복잡도 O(n²))

class Solution {
    public int[] solution(int[] prices) {
        
        // 각 시점별로 주식 가격이 떨어지지 않은 기간(초)을 저장할 배열
        int[] answer = new int[prices.length];
        
        // i번째 시점부터 가격이 떨어질 때까지 확인
        for (int i = 0; i < prices.length; i++) {
            
            // i 이후의 시점들을 하나씩 비교
            for (int j = i + 1; j < prices.length; j++) {
                answer[i]++; // 비교할 때마다 1초 증가
                
                if (prices[i] > prices[j]) break; // 가격이 떨어지면 종료
            }
        }
        return answer;
    }
}

• 이 풀이의 경우 이중 for문을 사용하므로 시간 복잡도가 O(n²)이다.
• 즉, 주식 가격이 10만 개라면 약 100억 번의 비교를 하게 된다.
• Stack을 사용하게 되면, 아직 가격이 떨어지지 않은 시점들의 인덱스를 저장해두고 새로운 가격이 들어올 때마다 그 가격과 비교해서 떨어진 시점을 한 번에 처리할 수 있다.

💡 두번째 풀이 (Stack -> 시간 복잡도 O(n))

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        
        // 각 시점별로 '가격이 떨어지지 않은 기간(초)'을 저장할 배열
        int[] answer = new int[prices.length];
        
        // 스택에는 아직 '가격이 떨어지지 않은 시점(index)'을 저장
        Deque<Integer> stack = new ArrayDeque<>();
          
        // 모든 시점을 순회
        for (int i = 0; i < prices.length; i++) {
            // 스택이 비어있지 않고, 현재 가격이 스택 top의 가격보다 낮으면, 가격 하락 발생
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                // 떨어진 시점의 index 꺼냄
                int prev = stack.pop();
                // 현재 시점 i까지 걸린 시간 저장
                answer[prev] = i - prev;
            }
            // 아직 안 떨어진 시점(index)을 스택에 저장
            stack.push(i);
        }
        
        // 끝까지 가격이 안 떨어진 시점들 처리
        while (!stack.isEmpty()) {
            int prev = stack.pop();
            // 마지막까지 안 떨어졌으므로 남은 전체 시간
            answer[prev] = prices.length - prev - 1;
        }
        
        return answer;
    }
}

• 각 인덱스는 최대 한 번 push, 한 번 pop 되므로 시간 복잡도는 O(n)이다.