[JAVA 문제 풀이] 340. 주식가격

내가 작성한 코드

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                answer[i]++; // 매 초 증가
                if (prices[i] > prices[j]) break; // 떨어지는 순간 멈춤
            }
        }

        return answer;
    }
}

다른 사람의 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> beginIdxs = new Stack<>();  // 인덱스를 저장할 스택
        int i = 0;  // 현재 시간(초)를 나타냄
        int[] answer = new int[prices.length];

        beginIdxs.push(i);  // 0번 인덱스를 스택에 넣음
        
        // 1번 인덱스부터 prices 끝까지 순회
        for (i = 1; i < prices.length; i++) {
            // 현재 가격이 이전 스택의 top보다 낮은 경우 = 가격이 떨어졌다는 의미
            while (!beginIdxs.empty() && prices[i] < prices[beginIdxs.peek()]) {
                int beginIdx = beginIdxs.pop();  // 떨어진 시점 이전의 인덱스 꺼냄
                answer[beginIdx] = i - beginIdx;  // 해당 인덱스부터 떨어진 시점까지 지속된 시간 저장
            }

            beginIdxs.push(i);  // 현재 인덱스를 스택에 저장 (가격이 안 떨어졌거나 계속 상승 중)
        }

        // 마지막까지 가격이 떨어지지 않은 항목 처리
        while (!beginIdxs.empty()) {
            int beginIdx = beginIdxs.pop();  // 남아있는 인덱스
            answer[beginIdx] = i - beginIdx - 1;  // 끝까지 안 떨어졌으므로 전체 지속 시간 계산
        }

        return answer;
    }
}

• Stack을 활용해 시간 복잡도를 줄이는 방식