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

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

프로그래머스

 

 

사용 알고리즘

 

• 스택

풀이

 

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        // 1. 다음 값이 현재 값보다 작을 때 
        // 2. 다음 값이 현재 값보다 클 때 -> 
        
        Stack<Integer> s = new Stack<>();
        for(int i = 0; i < prices.length; i++){
            
            while (!s.isEmpty() && prices[i] < prices[s.peek()]) { // 다음 값이 현재 값보다 작다면, 
                answer[s.peek()] = i - s.peek(); 
                s.pop(); // 제거
            }
            
           
            s.push(i);
        }
        
        while(!s.isEmpty())  {
            int cur = s.peek();
            answer[cur] = prices.length - cur - 1;
            s.pop();
              
        }
        return answer;
    }
}

 

 

회고

 

직관적으로 와닿지 않는 문제였다. 하나씩 찍어보면서 동작 방식이 어떻게 되나 확인하는게 많은 도움이 되었다

 

배열을 순회하면서 먼저 생각해야 될 부분은, 다음 원소가 현재 원소보다 큰지 작은지 여부이다.

 

다음 원소가 크다면 문제가 되지않지만, 작을 때 케이스가 중요하다. 

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

 

위 예제를 보면 3에서 2로 떨어지는 부분에서 1초로 값이 초기화가 된다. 그래서 값을 answer에 바로 박아버리면 해결 된다.

 

Stack에 남아있는 인덱스는 값이 떨어지는 시점인 2을 제외하고 [0,1,3,4]가 남아있으므로 순회를 돌면서 answer에 할당해주면 된다.