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

문제 설명

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

프로그래머스

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

제한 사항

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

입출력 예

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

입출력 예 설명

입출력 예 #1

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

내가 작성한 코드

class Solution {
    public int[] solution(int[] prices) {
        // 결과를 저장할 배열 생성
        int[] answer = new int[prices.length];
        
        // i : 현재 가격의 시점
        for (int i = 0; i < prices.length; i++) {
            // j : 다음 시점부터 끝까지 확인
            for (int j = i+1; j < prices.length; j++) {
                // 가격이 떨어지지 않았을 때 시간 1초 경과
                answer[i]++;
                // 만약 가격이 떨어졌다면
                if (prices[i] > prices[j]) {
                    // 반복문 종료
                    break;
                }
            }
        }
        // answer 반환
        return answer;
    }
}

문제를 풀기 위해 생각한 방향

Stack을 사용하지 않고 배열만으로도 문제를 풀 수 있을 것 같았다.
가격이 떨어지지 않을  각 자리 수를 계속 1씩 증가하면 정답을 반환할 수 있을 것이라고 생각했다.

Stack을 활용한 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        // 결과를 저장할 배열 생성
        int[] answer = new int[prices.length];
        // 인덱스를 저장할 Stack 생성 (가격이 떨어지지 않은 시점 저장)
        Stack<Integer> stack = new Stack<>();
        
        // 주식 가격 순회
        for (int i = 0; i < prices.length; i++) {
            // Stack이 비어있지 않거나 현재 가격이 이전 가격보다 큰 경우
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                // 떨어진 시점까지 걸린 시간 계산
                answer[stack.peek()] = i - stack.peek();
                // Stack에서 제거
                stack.pop();
            }
            // 떨어지지 않은 시점 저장
            stack.push(i);
        }
        
        // Stack에 남아 있는 인덱스 확인
        while(!stack.isEmpty()) {
            // 마지막까지 유지된 시간 계산
            answer[stack.peek()] = prices.length - stack.peek() - 1;
            // Stack에서 제거
            stack.pop();
        }
        
        // answer 반환
        return answer;
    }
}

문제를 풀기 위해 생각한 방향

Stack을 활용한 방법은 어떻게 접근해야할지 잘 모르겠어서 다른 풀이 방법들을 찾아보면서 이해하고 넘어갔다.
Stack을 잘 활용할 수 있다면 문제를 더 편하게 풀 수 있다고 생각했다.