99클럽 코테 스터디 4일차 TIL - 스택

항해99 코테 스터디 4일차 문제인 프로그래머스의 '주식가격'은 매초마다 주어지는 주식의 가격이 떨어지지 않은 기간을 구하는 문제다. 난이도는 레벨2이며 스택이나 우선순위큐를 통해 해결할 수 있다.

 

오늘의 문제 - 주식가격 문제 정보

문제 키워드

- 스택/큐

난이도

- Level 2

 

문제 요약

• 매초 주식의 가격이 배열로 주어질 때, 가격이 떨어지지 않은 기간을 가각 구하여라.

 

문제 풀이 과정  

• • 스택에 매초마다 가격을 삽입하는데, 삽입하기 전에 현재 가격보다 높은 요소들을 모두 꺼내 정답을 업데이트한다.
  • 또는 가격 내림차순으로 정렬되는 우선순위큐를 사용해 매초마다 가격을 삽입하고 현재 가격보다 높은 요소들을 모두 꺼내 정답을 업데이트한다.
  • 이 문제에서는 우선순위큐보다 스택을 이용한 방법이 좀 더 간편하다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int N = prices.length;
        int[] answer = new int[N];
        
        Stack<Price> stack = new Stack<>();
        for(int t=0; t<N; t++) {
            int nowPrice = prices[t];
            
            // 현재 가격보다 높았던 때를 모두 pop
            while(!stack.isEmpty()) {
                if (stack.peek().p > nowPrice) {
                    Price price = stack.pop();
                    answer[price.t] = t - price.t;
                } else {
                    break;
                }
            }
            
            stack.add(new Price(t, nowPrice));
        }
        
        // 스택에 남은 거(가격이 끝까지 떨어지지 않은 것) 모두 꺼내면서 정답 배열 업데이트
        while(!stack.isEmpty()) {
            Price price = stack.pop();
            answer[price.t] = N - price.t - 1;
        }
        
        return answer;
    }
    
    class Price {
        int t;
        int p;
        
        public Price(int t, int p) {
            this.t = t;
            this.p = p;
        }
    }
}

• 시간복잡도: O(N)
• 공간복잡도: O(N)

 

오늘의 학습 회고

새롭게 알게된 것

• 항상 더 간단한 풀이방법이 있는지도 고민해보자.
• 스택/큐 등 기본적인 자료구조의 사용법은 까먹지 말고 기억해두자