알고리즘 풀이 - 프로그래머스(주식가격, 스택)

 

문제 설명

 

초 단위로 기록된 주식가격이 담긴 배열 prices가 주어질 때, 가격이 떨어지지 않은 기간이 몇 초인지 return하는 문제

 

제한 사항
 - prices의 각 가격은 1 이상 10,000 이하인 자연수
 - prices의 길이는 2 이상 100,000 이하

 

예시

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

1초 시점의 price 1은 2, 3, 2, 3 의 4초가 지날 동안 떨어지지 않아 4초
2 초 시점의 price 2는 3, 2, 3 의 3초가 지날 동안 떨어지지 않아 3초
3 초 시점의 price 3은 다음의 2로 떨어져 1초
4 초 시점의 price 4는 떨어지지 않아 1초
5 초 시점의 price 3은 마지막이므로 더 이상 체크할 수 없어 0초

 

 

해결 방안 1 - Stack을 이용

 

Stack을 두 개를 써서 할 수도 있고, 한 개를 써서 만들 수도 있다. 여기서 보일 코드는 Stack 1개를 이용해서 풀어낸 방식으로 시연하겠다. 우선 코드를 보자

import java.util.Stack;
class Solution {
    public int[] solution(int[] prices){
        int[] answer = new int[prices.length];
        Stack<Price> stack = new Stack<>();
        for(int i=0; i < prices.length; i++){
            int current = prices[i];
            while(!stack.isEmpty()){
                Price top = stack.peek();
                if(top.price > current){
                    answer[top.index] = i - top.index;
                    stack.pop();
                } else {
                    break;
                }
            }
            stack.push(new Price(i, current));
        }
        while(!stack.isEmpty()){
            Price top = stack.pop();
            answer[top.index] = prices.length - 1 - top.index;
        }
        return answer;
    }
    private class Price{
        int index;
        int price;
        public Price(int index, int price){
            this.index=index;
            this.price=price;
        }
    }
}

 

Price 라는 private inner class를 만들어 index와 price 값을 저장하여 객체로써 활용해 Stack에 저장하는 방식으로 진행했다.

일단 배열을 index 0부터 시작하여 반복문을 취한다. 이 때, 현재 값은 배열의 i 번째 값을 갖고 진행한다. Stack에는 이전 배열의 반복문을 통해 삽입된 Price 객체가 들어 있다. 즉, 현재 Stack에 있는 값들은 1 ~ i초 전의 주식가격이라고 볼 수 있다. 이전의 값들보다 현재 값이 더 작다면 이전의 값들에서 가격이 하락한 것이라고 볼 수 있다.

따라서, Stack에 있는 객체를 체크하여 현재 price보다 크다면 그 index와 현재 index 값의 차이의 초(second)만큼 지나서 가격이 하락했다고 볼 수 있다. 그 후, 현재의 객체도 다시 Stack에 넣어준다. 마지막으로 Stack에 아직 남아있는 객체는 가격이 떨어지지 않은 상태라는 의미이므로, 배열의 길이 - 1과 각 객체의 index의 차이만큼이 답이라고 볼 수 있게 된다.

해당 코드의 테스트 결과는 다음과 같다.

 

 

 

해결 방안2 - 배열로 풀기

 

코드는 아래와 같다.

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

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

2중 for 반복문을 통해서 현재 값과 이후의 값들을 모두 비교해 더 작아졌으면 그 차이를 구하여 저장 후 반환하는 방식이다. 이 방식이 더 이해는 하기 쉽다. 해당 코드의 테스트 결과는 다음과 같다.

 

 

배열을 이용한 쪽이 훨씬 빨랐다.

 

Stack 2개를 이용해서도 간단히 풀 수는 있다. 아래의 포스팅을 참고하여 방법을 연구하면 되겠다.

https://hongjw1938.tistory.com/8