1. 문제에 대하여 📦

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584

(1) 조건 분석 📊

매초 주식 가격이 하나씩 나온다.
하나의 주식 가격이 그 밑으로 떨어지지 않은 기간을 구하여라

[!example]
[3,1,2,3] 으로 각 초마다의 주식 가격이 주어졌을 경우,
0초의 주식 가격은 그 다음 초에 1로 바로 떨어진다. 따라서 가격이 떨어지지 않은 기간은 1초이다.
반면 1초대의 주식가격은 주식 가격 배열이 끝날 때까지 그보다 밑으로 떨어지지 않는다.

2. 코드가 나오기까지 🛠️

KEY WORD: STACK 활용

STOCK이란 클래스를 만든다. 멤버변수는 해당 주식 가격이 나왔던 초(index)와 가격(price)이다.
STACK에 존재하는 값들은 아직 그보다 가격이 떨어지지 않아서, 매 번 가격 유지 기간이 갱신되어야 하는 값들이다. 따라서 다음과 같이 계산을 한 후, STACK에 남아있는 모든 값들에 대해 유지 기간을 +1 올린다.

STACK이 비어있을 때는 현재 초의 주식 가격을 넣는다.
STACK이 비어있지 않을 때는 STACK TOP의 주식 가격과 현재 초의 주식 가격을 비교하여 계산한다.
(1) STACK TOP의 주식가격보다 현재 초의 주식가격이 높다면, 그대로 STACK에 넣는다.
(2) 반대의 경우 TOP을 POP하고, 2번을 다시 한다.
STACK의 남아있는 모든 값들은 아직 그보다 가격이 떨어지지 않은 값들임으로, 해당 값들이 가격 유지 기간을 갱신한다.

(1) 시간복잡도 분석 ⏳

나올 수 있는 주식 가격의 개수는 100,000건이다. $10^{5}$ 이라 시간 복잡도가 $O(n^{2})$ 되면, 문제를 풀지 못할 수 있다. 100,000건을 하나씩 확인한다. 하지만 1건마다 100,000건 전체를 훑지 않기 때문에 $O(n^{2})$ 보단 훨씬 시간 복잡도가 작을 것이라 예상된다.

3. 코드 🌐

import java.util.*;

class Solution {

    static class Stock {
        int index;
        int price;

        public Stock(int index, int price){
            this.index = index;
            this.price = price;
        }

        @Override
        public String toString(){
            return "(원래 위치: " + index + " 가격: " + price + ")";
        }
    }


    public int[] solution(int[] prices) {
        int [] answer = new int[prices.length];
        int iter = -1;
        Stock [] stack = new Stock [prices.length];

        for(int i = 0; i < prices.length-1; i++){
            // 당초 주식 넣기
            if(iter == -1) stack[++iter] = new Stock(i, prices[i]);
            else {
                while(iter >= 0 && stack[iter].price > prices[i]){
                    iter--;
                }
                stack[++iter] = new Stock(i, prices[i]);
            }
            // 하루가 흐름.
            for(int j = 0; j <= iter; j++){
                answer[stack[j].index]++;
            }
        }

        return answer;
    }
}