[Programmers] 주식가격

문제 설명

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

제한사항

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

• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

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

 

---

풀이

이 문제를 스택을 활용해서 풀려고하니 생각보다 시간이 오래걸렸다..(스택/큐 문제에 약함ㅠ)

문제의 핵심은 타겟 숫자 기준으로 뒷쪽에 큰 숫자는 고려하지 않아도 되고, 작은 숫자의 인덱스만 고려하면된다. 예를 들어 {4,5,2,1} 의 경우, 4는 5는 고려하지 않고 떨어지는 부분인 2의 위치(인덱스)만 알면 된다. 타겟 숫자보다 작은 숫자가 나올 때까지 뒤의 숫자들을 전부 찾아봐야 하는 문제는 역으로 생각해서 스택을 사용하여 해결할 수 있다. 

 

먼저 얼마나 주식 가격을 유지했는지 (유지기간) 와 주식가격 정보를 사용하기 위해 int 배열을 선언하고 0번째에 유지기간, 1번째에 주식가격을 넣고 이를 스택에 넣는 방식으로 생각하였다. 마지막 주식가격은 유지기간이 항상 1이므로 순회(for문)의 시작은 '마지막 인덱스-1' 부터 시작하였다.

 

뒤에서부터 순회할 때 타겟 숫자보다 큰 숫자가 스택의 top에 있다는 것은 그만큼의 유지기간 동안 주식가격이 떨어지지 않은 것으로 타겟 숫자의 유지기간에 지금까지 유지한 기간(스택의 top의 유지기간)을 더해준다. 만약 타겟 숫자가 스택의 top의 숫자보다 크다는 것은 주식가격이 떨어지는 구간으로 스택에 넣어준다.

코드

import java.util.*;

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