문제 출처

코딩테스트 연습 > 스택/큐 > 주식가격
https://school.programmers.co.kr/learn/courses/30/lessons/42584

문제 설명

주식 가격 배열 prices 가 주어질 때, 배열의 각 요소들이 가격이 떨어지지 않은 기간 배열로 return 하라.

접근 방법

이 문제는 간단하게 중첩 for문을 이용하여 비교하려는 대상 뒤에 있는 요소들을 하나씩 비교하면서(비교할 때마다 count를 증가시킨다.) 가격이 떨어지는 순간에 안 쪽 for문을 끝내어 기록해주면 된다.

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

Review
다른 사람들이 풀이한 stack을 기반하여 푼 풀이이다. 앞에 설명한 것 처럼 prices의 인덱스를 스택에 삽입한다. 그리고 for문을 통해 prices의 현재 index에 해당하는 값과, stack에 가장 위에 있는(peek) index에 해당하는 값을 비교하여 만약 현재 index에 해당하는 값이 더 작으면 스택에서 pop을 통해 index 값을 추출하여 결과 배열인 answer[index]에 먼저 값을 계산해서 넣는다.

import java.util.*;

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

알게된 점

처음 풀 때, 이 문제가 왜 스택/큐 에 속하는 문제인지 이해할 수 없어서 그냥 내가 이해한대로 풀었다. 생각보다 간단한 문제였지만, 이후 다른 사람들이 스택을 이용해서 푼 것을 보니 신기했다. 스택으로 푸는 방법은 비교하는 index를 스택에 넣어 현재 index와 스택에 넣은 index를 peek 했을 때, peek한 index의 배열 값이 더 큰 경우 결과를 return하는 배열에 현재 index - pop한 index의 계산 값을 넣는 것이다.

% 이해는 했지만, 막상 글로 써보니 설명하기가 어렵다.

% 코드를 이해하던 중 prices가 {3, 3, 7, 8, 4} 와 같이 들어오면 결과가 제대로 안나오는 것 아닌가 생각했더니, for문 안 while문의 조건으로 prices[i] < prices[st.peek()]가 들어 있으므로 7이 4로 떨어졌을 때 경우도 잘 계산한다.

문제푼 흔적

Review