[lv.2] 주식가격

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

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

• 풀이1 : 반복문 O(n^2)
  간단하다. 배열의 처음부터 끝까지를 i라고 할때 i+1부터 끝까지 올라가느냐 내려가느냐를 살펴본다. 이게...되네...

import java.util.*;

class Solution {
    public int[] solution(int[] p) {
        int[] answer = new int[p.length];
        for(int i=0; i<p.length; i++){
            for(int j=i+1; j<p.length; j++){
                answer[i]++;
                if(p[i]>p[j]) break;
            }
            
        }
        return answer;
    }
}

• 풀이2 : 스택
  사실 이게 정말 어렵다. 발상부터가 매우 어렵다.
  1) stack과 answer배열을 만든다.
  2) 0번부터 끝까지 반복문을 돌며 p[i]>=prices[stack.peek()]일 경우 가격이 감소하지 않음, stack에 i를 push
  3) 감소한다면 주식이 감소한 시점, stack에서 해당 인덱스를 제거 이후 answer[stack.peek()]에 i-stack.peek() 값을 넣는다. (즉, 주식의 감소 시점 - 주식이 처음 들어간 시점)
  4) 값을 구하지 못한 인덱스는 사실상 끝까지 가격이 떨어지지 않았다는 것. 해당 인덱스에 p.length-index-1을 넣는다.

import java.util.*;

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

}

//출처 : https://girawhale.tistory.com/7