[스택/큐] 프로그래머스 42584번 주식가격(Java)

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

프로그래머스

📚 문제

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

제한사항

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

 

📝 문제 해결

이중 반복문을 통해 배열의 값을 하나씩 비교하며 가격이 떨어지지 않은 경우 answer을 1초씩 증가시키고, 만약 가격이 떨어질 경우 prices[i] > prices[j]  반복문을 빠져나온다.

 

💻 코드

public class No42584 {
    public static void main(String args[]){
    	System.out.println(solution(new int[]{1, 2, 3, 2, 3}));
    }
    
    public static 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;
    }
}

 

+) 스택을 이용한 풀이

가격과 위치(인덱스)를 배열에 저장하여 Stack에 넣어주고 Stack의 마지막으로 넣어준 가격과 현재 가격을 비교하여

현재 가격이 더 낮다면 Stack에서 값을 꺼낸 뒤, 현재 기간(i) - 해당 기간(Stack의 마지막)을 넣어준다. (현재 기간이 더 높을 때까지  반복)

[출처 : https://after-newmoon.tistory.com/40 ]

import java.util.*;

public class No42584 {
    public static void main(String args[]){
    	System.out.println(solution(new int[]{1, 2, 3, 2, 3}));
    }
    
    public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer[]> stack = new Stack<>();
        
        for(int i = 0; i < prices.length; i++){
            answer[i] = answer.length - 1 - i;
            Integer[] arr = {i, prices[i]};
            
            while(!stack.empty() && stack.peek()[1] > prices[i]){
                Integer[] price = stack.pop();
                answer[price[0]] = i - price[0];
            }
            
            stack.push(arr);
        }
        
        return answer;
    }
}