문제

문제 분석

먼저 들어올 수록 값이 늦고 나중에 들어올 수록 값이 낮으므로 스택을 이용하여 값의 차이를 둘 수 있을 것이다.

---

풀이

스택 사용

import java.util.Stack;
Stack<> stack = new Stack<>();

을 이용하여 자바에서 쉽게 스택을 사용할 수 있다.

한문자씩 비교

prices[]의 현재 인덱스에 있는 값과 스택의 top에 있는 값을 비교해야 가격 하락여부를 확인 할 수 있다.

스택

값의 크기에 상관없이 주식 가격이 상승중이라면 항상 스택의 top 값이 현재 인덱스의 prices 값보다 작고 push된다. 반면 값이 하락이 오면 동일한 값이 나올때까지 스택의 위쪽에 위치한 값들은 pop()이 될 것이다.

for(int i=0;i < prices.length;i++){
       while(!stack.isEmpty() && prices[i] < prices[stack.peek()]){
           answer[stack.peek()] = i - stack.peek();
           stack.pop();
       }
       stack.push(i);
   }

stack 스택에는 prices배열의 인덱스가 저장된다. 인덱스로 유지된 시간을 계산하기 위해서이다.

stack.isEmpty()는 현재 스택이 비어있는지, stack.peek()은 스택의 top에 위치한 값을 리턴한다.
push(i)와 pop()은 각각 입력 출력(삭제) 이다.

유지시간

하락한 경우는 미리 유지시간을 기록하였으므로 스택에 남아있는 하락하지 않았던 값들의 유지시간을 기록해야한다. 주식시장이 끝나는 시점 = 배열의 끝나는 시점 = 배열의 길이 이므로 배열의 길이 - 스택내 인덱스의 값하면 하락하지 않았던 값의 유지시간을 구할 수 있다.

while(!stack.isEmpty()){
       answer[stack.peek()] = prices.length - stack.peek() - 1;
       stack.pop();
   }

---

코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<>();
        
        // i는 index
        for(int i = 0; i < prices.length; i++){
            while(!stack.isEmpty() && prices[i] < prices[stack.peek()]){ //i번째 인덱스와 stack의 top번째 `인덱스` 비교
                answer[stack.peek()] = i - stack.peek(); //현재 인덱스 - 해당 인덱스
                stack.pop();
            }
            stack.push(i); // `인덱스 삽입`
        }
        
        // 스택에 남은 값들
        while(!stack.isEmpty()){
            //최대 길이에서 해당 길이만큼 빼줌
            answer[stack.peek()] = prices.length - stack.peek() - 1;
            stack.pop();
        }
        return answer;
    }
}

---

GitHub

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%9E%90%EB%B0%94/Level2/%EC%A3%BC%EC%8B%9D%EA%B0%80%EA%B2%A9.java