[Lv.2] 주식 가격 : Java, Stack

 

프로그래머스

 

가격이 떨어지지 않은 기간 몇 초인지 return

전 가격 < 이후 가격 : 떨어짐, 카운트X

 

#(배열 크기-1)만큼 반복

0 : 1번째 원소부터 비교 => 떨어지면 카운트X

#마지막 원소는 0 리턴

 

#통과는 했지만 시간복잡도 O(n^2) 인 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        for(int i=0; i<prices.length-1; i++){
            int cnt = 0;
            int j = i+1;  // 비교할 원소
            while(j<=prices.length-1){
                cnt++;
                if(prices[i] > prices[j])
                    break;
                j++;
            }
            answer[i] = cnt;
        }
        answer[prices.length-1] = 0;
        return answer;
    }
}

 

#스택 활용 코드

“아직 가격이 떨어진 시점을 모르는 인덱스”를 스택에 저장

현재 가격이 이전 가격보다 낮아지면
→ 시간 차이 계산

=> 스택에는 아직 가격이 떨어지지 않은 인덱스를 넣고, 현재 가격이 더 낮아지는 순간 pop하면서 시간을 확정

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; 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] = n - 1 - idx;
        }

        return answer;
    }
}