[P&B] #26 Programmers

프로그래머스 Lv.2 스택

 

기능개발

문제 설명

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

 

제한 사항

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

나의 문제 풀이 코드 (6.7/100)

class Solution {
     public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        for (int i = 0; i < prices.length-1; i++) {
            int count = 0;
            for (int j = i+1; j < prices.length; j++) {
                if (prices[i]>prices[j]&&i==j-1) {
                    count = 1;
                    break;
                }
                else if (prices[i]<=prices[j]) {
                    count++;
                }
                else
                    break;
            }
            answer[i] = count;
        }
        answer[prices.length-1] = 0;
        return answer;
    }
}

 

다른 답안 코드

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = 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()]) {
                int index = stack.pop();
                answer[index] = i - index;
            }
            stack.push(i);
        }

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

        return answer;
    }
}

 

문제 풀이 코멘트

 이 문제 역시 for문으로 먼저 풀었는데 테스트코드만 통과하고 제출 시 한문제밖에 맞히지 못했다. 스택을 사용해야한다는 힌트를 얻고 다시 풀어보려고 했으나 스택에 넣은 값의 시간 카운팅을 어떻게 해결해야할지 풀지 못했다.

답안을 보았을 때 문제를 풀기 위해서는 배열을 순회하면서 각 시점에서 가격이 떨어지지 않은 기간을 구해야 한다. 이때, 스택(Stack)을 사용하여 효율적으로 구할 수 있다.

스택에는 가격이 떨어지지 않은 기간의 인덱스를 저장하면서 순회한다. 새로운 가격이 스택에 저장된 인덱스의 가격보다 작다면 스택에서 해당 가격의 인덱스를 꺼내면서 가격이 떨어지지 않은 기간을 계산한다. 즉, 스택을 사용하여 주식가격의 인덱스를 저장하면서 순회하면서 가격이 떨어지지 않은 기간을 계산한다.

• 스택이 비어있지 않고, 현재 가격이 스택에 저장된 가격보다 작다면, 가격이 떨어지는 순간이 발생한 것이다. 이때 스택에서 해당 가격의 인덱스를 꺼내면서 가격이 떨어지지 않은 기간을 계산한다. 현재 인덱스 i에서 스택에서 꺼낸 인덱스를 뺀 값이 가격이 떨어지지 않은 기간이 된다. 이를 answer 배열에 저장한다.
• 현재 인덱스 i를 스택에 push 한다.

prices 배열을 모두 순회한 후에도 스택이 비어있지 않다면, 가격이 떨어지지 않은 기간이 끝나지 않은 것이다. 스택에 저장된 인덱스들은 가격이 떨어지지 않은 기간이 끝나지 않은 마지막 시점들이다. 따라서 해당 인덱스들에 대해 끝까지의 기간을 계산하여 answer 배열에 저장하고 반환한다.

스택에서 해당 가격의 인덱스를 꺼내면서 가격이 떨어지지 않은 기간을 계산하는 부분의 풀이 방법을 생각해내지 못해 어려웠던 문제였다.