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

링크

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

프로그래머스

 

문제 요약

초 단위 주식가격 배열 prices에 대해 가격이 떨어지지 않은 기간은 몇 초인지 반환하기

• 예: [1,2,3,2,3] → [4,3,1,1,0]

 

제한

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

 

풀이

prices의 길이가 최대 10^6이므로 시간 복잡도는 `O(N)` 이어야 합니다.

따라서 i초 시점 주식 가격이 언제 떨어지는지 그 뒤를 매번 확인한다면, `O(N^2)`이므로 이 방식으로 풀이하면 시간 초과가 날 것입니다.

 

O(N)으로 풀려면, prices 원소를 하나씩 순회하면서 동시에 정답도 업데이트해야 됩니다.

그러면 정답을 업데이트하는 시점은 언제일까요?

 

주어진 예제를 한 번 살펴봅시다.

[1,2,3,2,3]

• idx=1, idx=2, idx=4: 이전 값보다 크면 업데이트할 필요 없습니다.
• idx=3: 이전 값보다 작아졌으므로 idx 2의 정답을 업데이트해야 합니다.
  • idx 1의 정답은 원소 값이 동일하므로 업데이트하지 않아도 됩니다.
  ⇒ 이전 값보다 작은 값이 나오면 그 전의 인덱스들의 정답을 업데이트해야 할 수도 있습니다.
• 예제에는 없지만 이전 값보다 동일한 값이 나왔을 때도 업데이트할 필요 없습니다.
  • ex. [1,2,2], [3,2,2] → 두 상황 모두 두 번째 2에서는 정답을 업데이트하지 않습니다.

따라서 정답을 업데이트하는 시점은 “이전 값보다 작은 값이 나왔을 때”입니다.

 

근데 문제는 이 시점에서 앞선 인덱스의 정답이 확정될 수도 있고, 아닐 수도 있습니다.

 

따라서 앞으로 하나씩 가면서 정답을 확정할지 말지를 결정하면 됩니다.

만약 idx 3에서 앞선 인덱스의 정답을 업데이트해야 할 때, idx 2의 정답은 확정되지 않았는데 idx 1의 정답만 확정되는 경우는 없습니다. idx 3 이전에 정답이 확정되지 않은 상태였다는 것은 idx 1 ≤ idx 2 이기 때문입니다.

 

알고리즘을 정리하면 다음과 같습니다.

1. `idx=i`에 대해 `prices [i]<prices [i-1]`인지 확인한다.
   1. 만약 맞다면, 정답이 확정되며 정답은 `i-(i-1)`이다.
      1. 인덱스 `i-2`의 정답이 확정되지 않았다면, `prices [i]<prices [i-2]`인지 확인한다.
         1. …
   2. 아니라면, `i`의 값을 1 증가시킨다.
2. 마지막에 정답이 확정되지 않은 모든 인덱스들은 정답이 `(prices의 길이)-1-(자신의 인덱스)`입니다.

`i` 값은 앞에서부터 증가하지만(후입), 정답 확정 여부를 검사할 때 뒷번호부터 검사합니다.(선출)

따라서 인덱스를 저장하는 스택을 활용하면 됩니다!

 

정답이 확정되지 않은 인덱스는 스택에 push 하고, 정답이 확정되는 시점에 pop 하는 알고리즘을 생각할 수 있습니다.

 

코드

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[prices.length];
        stack.push(0);
        int i;
        for(i=1; 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] = i-idx-1;
        }
        
        return answer;
    }
}

🏷 시간 복잡도

• `N`: prices의 길이
• stack을 기준으로 prices의 원소들이 한 번씩만 push, pop 됩니다.
  • push 연산: N번
  • pop 연산: N번
  • `O(N+N)` = `O(N)`
• 최종 시간 복잡도: `O(N)`

🏷 실행 속도

Time: 37.95 ms, Memory: 73.5 MB