[프로그래머스] 주식가격

문제

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

제한사항

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

입출력 예

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

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42584

생각

• prices 배열을 2번 반복하면서(i,j) i 번째 가격보다 작은 j번째 가격이 나올 때까지 걸린 시간을 count해서 배열에 넣자

코드

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

        for (int i = 0; i < prices.length - 1; i++) {
            int time = 0;
            for (int j = i + 1; j < prices.length; j++) {
                time++;
                if (prices[i] > prices[j]) {
                    break;
                }
            }
            answer[i] = time;
        }

        return answer;
    }
}

다른 사람의 풀이

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> beginIdxs = new Stack<>();
        int i=0;
        int[] terms = new int[prices.length];

        beginIdxs.push(i);
        for (i=1; i<prices.length; i++) {
            while (!beginIdxs.empty() && prices[i] < prices[beginIdxs.peek()]) {
                int beginIdx = beginIdxs.pop();
                terms[beginIdx] = i - beginIdx;
            }
            beginIdxs.push(i);
        }
        while (!beginIdxs.empty()) {
            int beginIdx = beginIdxs.pop();
            terms[beginIdx] = i - beginIdx - 1;
        }

        return terms;
    }
}

• 문제를 풀고 나서 이 문제가 왜 스택/큐 문제지...? 🤔 라는 의문이 들었는데 위 풀이를 보고 이해됐다
• 이중 반복문을 사용하지 않고서도 주식가격이 떨어지기 시작하는 시점의 인덱스beginIdx를 사용해 주식 가격이 떨어지지 않은 기간을 계산한 점이 인상적이었다