문제

문제링크

풀이

접근방법

힌트
풀지 못하고 질문하기에 있는 힌트를 참고했습니다.
이런 관점으로도 볼 수 있다는게 참 신기했습니다.

상승장과 스택

상승장, 즉 이전 가격보다 지금 가격이 같거나 크다면 스택에 계속 저장합니다.
이렇게 되면 가격이 떨어지게 되면 스택에 저장하는게 멈추게 되고, 스택에 쌓인 가격들은 모두 오름차순으로 쌓입니다.
주어진 예제에선 4번째 가격인 2가 왔을 때, 다음과 같이 스택이 쌓입니다.

---

Stack (시간, 가격)

l       l	Current
l (2,3) l	time 	: 3
l (1,2) l	price 	: 2
l_(0,1)_l

---

이제 현재 가격과 비교해서 더 크다면 계속 제거합니다. 현재 스택에서는 맨 위 (2,3)이 제거됩니다.
제거된 정보는 바로 정답에 갱신시킵니다. 현재 시간이 3이고, 제거된 정보의 시간은 2입니다.
정보의 시간은 결국 정답의 인덱스와 일치하므로 코드는 다음과 같습니다.

answer[info[0]] = currentTime - info[0];

제거가 끝났다면 이제 현재 (시간, 가격)을 스택에 넣어주고 똑같이 진행합니다.

---

Stack (시간, 가격)

l       l	
l (3,2) l	
l (1,2) l	
l_(0,1)_l

---

이렇게 끝까지 진행하고 마지막까지 스택에 남아있는 정보들은 끝까지 상승만 했으므로 정답도 그에맞게 갱신해줍니다.

// 상승장 스택에 남아있는 정보들은 넣은 시점부터 끝까지 떨어지지 않았으므로, 최대시간에서 빼줍니다.
int time = prices.length - 1;
while (!rising.isEmpty()) {
   int[] info = rising.pop();

   answer[info[0]] = time - info[0];
}        
return answer;

마지막까지 진행한 경우, 정답 갱신은 다음과 같이 진행합니다.

---

Stack (시간, 가격)
time = 4
l (4,3) l	-> 4 - 4 = 0	answer[4] = 0
l (3,2) l	-> 4 - 3 = 1	answer[3] = 1
l (1,2) l	-> 4 - 1 = 1	answer[1] = 1
l_(0,1)_l	-> 4 - 0 = 4	answer[0] = 4

---

핵심은 상승장일 때 스택에 저장하면 자동으로 오름차순으로 저장되고, 떨어지는 시점과 비교할 때 차례대로 꺼내 비교하면 시간 순으로 비교할 수 있어 모두 떨어지지 않은 기간을 구할 수 있다는 것 입니다.

전체 코드

import java.io.*;
import java.util.*;

class Solution {
    
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        // 상승장 일 때, 주식정보를 저장하는 스택입니다.
        // [0] : 시간
        // [1] : 주식 가격
        Stack<int []> rising = new Stack<>();        
        
        for (int i = 0; i < prices.length; i++) {
            // 상승장 일 때, 스택에 넣어줍니다.
            if (rising.isEmpty() || rising.peek()[1] <= prices[i]) {
                rising.add(new int[] {i, prices[i]});
            }
            // 상승장이 끝났을 경우,
            else {
                popLowerThanCurrentPrice(rising, answer, prices[i], i);
                rising.add(new int[] {i, prices[i]});
            }
        }
        
        // 상승장 스택에 남아있는 정보들은 넣은 시점부터 끝까지 떨어지지 않았으므로, 최대시간에서 빼줍니다.
        int time = prices.length - 1;
        while (!rising.isEmpty()) {
            int[] info = rising.pop();

            answer[info[0]] = time - info[0];
        }        
        return answer;
    }
    
    private void popLowerThanCurrentPrice(Stack<int []> rising, int[] answer, int currentPrice, int currentTime) {
        // 현재 가격보다 높은 것들을 모두 빼고 정답을 갱신합니다.
        while (!rising.isEmpty() && rising.peek()[1] > currentPrice) {
            int[] info = rising.pop();

            answer[info[0]] = currentTime - info[0];
        }
    }
}