[프로그래머스] 주식가격(Stack) - JAVA

문제 링크

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

코딩테스트 연습 - 주식가격

 

1️⃣ 이중 반복문

풀이 과정

처음 문제를 보자마자 이중 반복문으로 풀면 좋겠다고 생각했다.

0번 index부터 반복문을 돌며 해당하는 index 다음에 감소하는 주식 가격이 나올 때까지 answer[index]값을 증가시켜준다면 쉽게 나오기 때문이다.

 

코드

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

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                ans[i]++;
                if (prices[i] > prices[j]) 
                    break;

            }
        }

        return ans;
    }
}

 

2️⃣ Stack

풀이 과정

하지만 위의 이중 반복문으로 문제를 풀게 될 경우 시간 복잡도는 $O(n^2)$​이 되고, prices의 길이 범위가 10만이므로 최악의 경우 100억, 약 100초의 시간이 소요되게 된다 (1억당 1초라고 가정)

해당 문제에서는 이런 테스트 케이스가 없는 것 때문인지 효율성 부분도 쉽게 통과되었지만 스택을 활용한 방법도 알아보자

 

 

초기 생성했을 때의 모습이다. 빈 stack과 결과를 저장할 ans배열을 prices의 길이에 맞게 생성하였다

 

 

 

 

0번부터 n-1까지 반복문을 돌며 prices[stack.peek]과 비교하여 주식이 감소하지 않았다면 stack에 시간 index를 push한다.

 

 

 

만약 감소하는 값이 등장한다면 주식이 감소한 시점이므로 stack에서 해당 인덱스를 제거하고 i(현재 주식의 감소 시점) - stack.peek(주식이 처음 들어간 시점) 값을 ans[stack.peek]값에 넣어준다

 

 

 

 

i == 3일 때, 반복문을 돌고 난 뒤의 모습이다. prices[3]의 가격인 4보다 작은 인덱스를 가진 값들이 stack에서 제거되고 ans값들이 갱신되었다

 

 

 

 

반복문을 끝까지 돌았을 때, stack에는 제일 마지막에 추가된 4만이 존재하게 된다.
stack에 끝까지 남아 있는 경우는 끝까지 주식 가격이 떨어지지 않는 경우이므로, stack이 비어있을 때까지 prices의 길이 - index - 1를 넣어준다.

 

코드

class Solution {
    public int[] solution(int[] prices) {
        int[] ans = new int[prices.length];
        Stack<Integer> stack = new Stack();

        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                ans[stack.peek()] = i - stack.peek();
                stack.pop(); // 답을 구했기 때문에 stack에서 제거한다
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
            ans[stack.peek()] = prices.length - stack.peek() - 1;
            stack.pop();
        }

        return ans;
    }

}