[프로그래머스 고득점 kit] 스택/큐 Level2 주식 가격

문제 설명

 

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

제한사항

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

입출력 예

 

prices                                                                                                            return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

 

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

접근 방법

 

문제 자체를 이해 한다면 이중 for문으로 금방 풀리는 문제이다.

 

1. answer 배열을 해당 시점의 주식 가격이 떨어지는 시점의 최대 시간으로 초기화한다.

2. 주식이 떨어지지 않는 시간을 계산한다.

 

[1, 2, 1, 3, 2] 배열이 입력으로 주어진다면, 2초 시점의 주식 가격 2는 3초 시점에 1로 떨어지기 때문에 1초간 주식 가격이 떨어지지 않는다. 4초 시점에 다시 3으로 오르지만 1초간 가격이 떨어지지 않았다는 점에 변동은 없다.

 

[1, 2, 2, 1, 2] 배열이 입력으로 주어진다면, 2초 시점의 2는 4초 시점에 1로 떨어져 2초간 주식 가격이 떨어지지 않았다. 

 

위 두 예시의 시간 차는 배열 인덱스의 차이로 표현될 수 있다. 즉 1번 인덱스 요소(2초 시점)인 2는 3번 인덱스(4초 시점) 차례에서 1로 떨어진다. 따라서 3 - 1 = 2 초간 주식 가격은 떨어지지 않는다.

 

 

코드

 

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

 

 

느낀 점

 

이중 for문으로 효율성 부분도 해결되어 어려운 문제는 아니었다. 다만 문제에 대한 이해가 부족하여 테스트 케이스를 잘못 설정해 문제 해결에 많은 시간이 소요되었다.

 

그리고 스택/큐를 사용하여 풀지 않았는 데 사용하는 방법에 대해 알아보아야겠다.

 

 

스택을 이용한  풀이

 

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        int i = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(i++);
        
        for(;i<prices.length;i++){
            while(!stack.isEmpty() && prices[i] < prices[stack.peek()]){
                int idx = stack.pop();
                answer[idx] = i - idx;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int idx = stack.pop();
            answer[idx] = answer.length - 1 - idx;
        }
        return answer;
    }
}