[프로그래머스] Java Lv2. 코딩테스트 연습 > 스택/큐 > 주식가격 42584

문제설명

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

 

접근방법

1. 일일히 다 체크하면(완전탐색) 시간복잡도는 O(n^2)가 될 것이며 이는 의도한 바가 아닌것 같다.
2. 시간복잡도를 O(n)으로 줄이기 위해선 큐 또는 스택을 사용하여 prices[i]의 값과 튀어나올 값을 비교해야 된다.
3. 큐에 들어간 첫번째 값과 prices[i] 비교 vs 스택에 들어간 마지막 값과 prices[i] 비교
4. 스택에 prices[i]를 이전 값보다 큰 값이면 쌓고, 작은 값이면 가장 큰 수가 될 때까지 스택을 비운 후 추가하면 크기 비교를 한번만 할 수 있게 됨.
5. 스택을 비울 때 마다 비운 값과 prices[i] 사이에 숫자가 몇 개 있었는 지 카운트하여 answer에 추가

핵심로직

1. 스택에 들어있는 값(a) <= prices[i] 이면 prices[i] 을 스택에 넣어주고, a < prices[i] 이면 i와 a의 index를 비교해 answer[index]에 넣어주고 a를 pop
2. a가 빠지면 그 전 값 b와 prices[i]를 비교해 1번 과정을 반복

입출력 예

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

코드 작성(1차)

우선 값을 비교하기 위한 stack과 그 값의 index를 보관하는 stack을 생성해 각각 관리하였다.

import java.util.*

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> priceStack = new Stack<>();
        // count 계산을 위한 index stack 생성
        Stack<Integer> indexStack = new Stack<>();
        priceStack.add(prices[0]);
        indexStack.add(0);
        
        for(int i=1; i<prices.length-1; i++) {
            int currentNum = prices[i];
            // prices[i]보다 스택 숫자가 작으면 카운트 하고 스택에서 pop
            while(priceStack.size() > 0 && priceStack.peek() > currentNum) {
                int index= indexStack.pop();
                answer[index] = i-index;
                priceStack.pop();
            }
            // prices[i]보다 작은 숫자가 제거된 stack에 prices[i] 추가
            priceStack.add(currentNum);
            indexStack.add(i);
        }
        return answer;
    }
}

return값이 [0, 0, 1, 0, 0] 이 나온다. 디버그를 해보니 while문 안에 index = 3 인 경우만 들어가고 있다.

주식 값이 작아지면서 배열이 끝나다 보니 for문을 다 돌려도 스택 안에 있는 주식 값들이 카운트 되지 않고 메서드가 끝나는 상황.

코드 작성(2차)

stack에 남아 있는 값들을 처리하기 위해 while문을 추가하여 prices의 index 별로 몇 번 연속 가격이 하락하지 않았는지 카운트 해주었다.

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> priceStack = new Stack<>();
        Stack<Integer> indexStack = new Stack<>();
        priceStack.add(prices[0]);
        indexStack.add(0);
        
        for(int i=1; i<prices.length-1; i++) {
            int currentNum = prices[i];
            while(!indexStack.isEmpty() && priceStack.peek() > currentNum) {
                int index= indexStack.pop();
                answer[index] = i-index;
                priceStack.pop();
            }
            priceStack.add(currentNum);
            indexStack.add(i);
        }
        while(!indexStack.isEmpty()) {
            int index= indexStack.pop();
            // (배열 마지막 index) - (stack에서 튀어나온 수의 index)
            answer[index] = (prices.length - 1) - index;
            priceStack.pop();
        }
        return answer;
    }
}

작성하고 보니 값을 넣어주는 stack이 필요 없을것 같다.  index를 넣어주는 stack만으로 배열의 값을 찾아 price 값을 처리한다.

코드 작성(최종)

import java.util.*;

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

        for (int i = 0; i < prices.length; i++) {
            while (!indexStack.isEmpty() && prices[indexStack.peek()] > prices[i]) {
                int index = indexStack.pop();
                answer[index] = i - index;
            }
            indexStack.push(i);
        }

        while (!indexStack.isEmpty()) {
            int index = indexStack.pop();
            answer[index] = prices.length - 1 - index;
        }

        return answer;
    }
}

이로써 시간복잡도 O(n)을 만족하는 알고리즘을 완성했다.