[Programmers] 스택/큐 : 주식가격 JAVA

💬 문제 설명

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

 

🚫 제한 사항

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

 

🔨 입출력 예

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

​

💻 Solution.java

• 프로그래머스에서 스택/큐 문제로 분류되지만, 스택을 어떻게 활용해야할지 감이 잡히지 않아 생각 나는대로 이중 반복문으로 구현해봤다.
• 첫번째 반복문은 기준 시점이 되는 i의 값이고 두번째 반복문은 i + 1초부터 마지막까지의 초를 나타낸다
• 진행 시간은 매초 1 초씩 증가하며, i초보다 작은 값이 나타나면 반복문을 중단해준다.

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int [prices.length];
        
        // i초의 시점을 기준으로 진행
        for(int i = 0; i < prices.length; i++){
            // i초 이후로 검사를 진행
            for(int j = i + 1; j < prices.length; j++){
                answer[i]++;

                if(prices[i] > prices[j]){   // i초보다 작은 값이 있다면 반복문 중단
                    break;    
                }
            }
        }
        
        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;
    }
}