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

프로그래머스 알고리즘 고득점 Kit의 스택&큐 파트 문제 중 하나인 '주식가격' 문제를 Java로 풀어보았다. 

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

프로그래머스

 

 내가 푼 코드는 아래와 같은데, 풀면서 stack&queue를 활용하지 못하기도 했고, 시간복잡도도 O(N^2)로 효율적이지 않아서 다른 방법을 찾아보려 했다. 

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] answer = new int[len];
        answer[len-1] = 0;
        for (int i = len-2; i >= 0; i--) {
            int pre_idx = i+1;
            while (pre_idx < len-1 && prices[i] <= prices[pre_idx])
                pre_idx++;
            answer[i] = pre_idx - i;
        }
        return answer;
    }
}

 

 

 그래서 다른 분들의 풀이를 보면서 찾은 인사이트를 통해서 아래와 같은 코드로 다시 작성해 보았다. 가장 중요하게 잡은 목표는 스택이나 큐를 사용한 코드를 만드는 것이었고, 그다음으로 앞선 코드보다 시간복잡도를 개선하는 것을 목표로 삼았다. 

 그렇게 나온 아래 코드는 '순회하면서 stack 내의 값들(즉, 이미 순회한 값들) 중 현재값보다 큰 값이 있다면, stack에서 pop 한다.'는 것을 기초로 삼는다. 앞서 순회한 값들 중 현재값보다 큰 값이 있다면, 그 말은 즉슨 해당 위치에서 그 값은 감소해 버렸다는 것이다. 그래서 그 값이 가격이 떨어지지 않은 기간은 (현재 위치 - 해당 값의 위치)가 된다. 

 나는 이 때, 그럼 그 값이 현재값보다 작은데, 그보다 앞에 있는 값이 현재값보다 크면 어쩌지? 하는 의문이 들었다. 왜냐하면 stack의 특성상, peek 위치에 있는 값이 pop 되지 않는 이상 그보다 앞에 있는 값에 접근할 수 없기 때문이다. 그런데 조금만 더 생각해 보면 이 문제는 문제가 아니라는 것을 알게 된다. 현재 위치를 i라고 해보자. i-1에 있는 값은 현재 위치에 있는 값보다 작다고 하면, 이는 pop 되지 않는다. 그런데 i-2 위치에 있는 값이 현재 위치의 값보다 크다. 그러면 value[i-1] < value[i] < value[i-2]가 된다. 즉, value[i-1] < value[i-2] 이고, 따라서 알고리즘에 따르면 i-1번째 위치를 탐색할 때, i-2는 이미 pop 되어있다. 그래서 이런 걱정을 할 필요가 없다. 

 이를 바탕으로 아래 코드를 보면, 우선 stack을 선언해준다. 여기서는 Stack 대신 Deque를 사용했는데, Stack이 이미 폐기되어, Deque 사용이 권장된다고 하길래 Deque를 사용했다. 자세한 이유는 아래 글을 참고했다. 

https://velog.io/@jhl221123/%EC%9E%90%EB%B0%94%EC%9D%98-Stack%EC%9D%80-%EC%99%9C-%EC%82%AC%EC%9A%A9%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-%EA%B1%B8%EA%B9%8C

자바의 Stack 클래스는 왜 사용하지 않는 걸까?

 

 그리고 for문으로 prices 배열을 순회한다. 그 안에서 while 문을 돌면서, 현재 순회 중인 인덱스(i)의 price보다 큰 price를 가진 stack 내 peek()을  모두 pop 해준다. pop 해주고 있는 인덱스는 현재 순회 중인 위치에서 감소한다는 의미이므로, 답에 (현재 순회 중인 위치 - 해당 요소의 위치)를 해준다. 

 마지막으로 stack 내 남은 요소들은 모두 끝까지 감소하지 않는다는 의미이므로 끝 인덱스(len-1)에서 해당 요소의 인덱스를 빼주면 답이 된다. 

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        //stack이 폐기된 class이기 때문에 대신 deque 사용
        Deque<Integer> stack = new ArrayDeque<Integer>();
        
        int len = prices.length;
        int[] answer = new int[len];
        stack.push(0);
        for (int i = 1; i < len; i++) {
            while (!stack.isEmpty() 
                   && prices[stack.peek()] > prices[i]) {
                int idx = stack.pop();
                answer[idx] = i - idx; 
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            answer[idx] = len - idx - 1;
        }
        
        return answer;
    }
}