주식가격

🔒 문제

🔑 풀이

import java.util.stream.IntStream;

class Solution {
    public int[] solution(int[] prices) {
        for (int index = 0; index < prices.length ; index++) {
            int targetPrice = prices[index];
            // 나보다 가장 가까운 작은애 index 찾기, 만약에 못찾으면 -1
            int nextLowerPriceIndex = IntStream.range(index, prices.length)
                                    .filter(i->prices[i] < targetPrice)
                                    .findFirst()
                                    .orElse(-1);
            // 나와 작은놈의 거리
            // 나보다 작은놈 없던데? -> 전체 길이 - 내 현재위치 - 1
            // 찾았어!  -> 그놈 위치 - 내 위치
            int distance = (nextLowerPriceIndex == -1) ? prices.length - index - 1 : nextLowerPriceIndex - index;
            prices[index] = distance;
        }
        return prices;
    }
}

🔧 풀이 최적화

import java.util.Stack;

public class Solution2 {
    public int[] solution(int[] prices) {
        // stack 에는 time Stack Index 를 담는다. (유지가 잘되고 있는 애들의 시간)
        // index 는 자리로 시간과 비례한다.

        // prices[stackIndex.top] = index - stackIndex.pop
        var timeStack = new Stack<Integer>();
        timeStack.push(0);

        // 가격이 떨어지는 애들 라운드별로 검사
        for (int index = 1; index < prices.length ; index++) {
            // 가격이 떨어진 애 -> 유지 못했으므로 바로 현재 index - timeStackIndex.top == 현재 위치 - 최근까지 크다고 유지된놈의 위치
            // index - timeStackIndex.pop 을 스택이 비지 않을 떄 까지 (과거 놈들) && 더 prices[index] < timeIndex.top 일 때까지 쭉 처리해줌.
            while (!timeStack.empty() && prices[timeStack.peek()] > prices[index]) {
                int recentElementIndex = timeStack.pop();
                prices[recentElementIndex] = index - recentElementIndex;
            }
            // 일단 이 단계까지는 그대로 유지된 경우
            timeStack.push(index);
        }

        // 가격이 떨어지지 않는 놈들은 모두 stack 에 담음.
        // stack 남아있는 친구들은 마지막까지 유지된 놈들임
        // 따라서 prices[stack.top] = prices.length - stack.top - 1
        while (!timeStack.empty()) {
            var remainTimeIndex = timeStack.pop();
            prices[remainTimeIndex] = prices.length - remainTimeIndex - 1;
        }
        return prices;
    }
// test용 코드
    public static void main(String[] args) {
        var testArray = new int[]{1,2,3,2,3};
        var answerArray = new Solution2().solution(testArray);
        // 43110
        for (int element : answerArray) {System.out.print(element);}
    }
}