[프로그래머스 Level 2] 주식가격

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

 

풀이

• 초 단위로 기록된 배열 prices가 주어진다.
• 가격이 떨어지지 않은 시간을 return 한다.

 

맨 처음에는 2중 for문을 사용해서 해당 인덱스와 이후의 인덱스를 비교해서 가격이 떨어질 때 까지 비교하는 방법으로 풀었다.

하지만 이 방법은 시간복잡도가 O(n^2)나 되기 때문에 다른 풀이를 생각해보았다.

 

순서대로 쌓인 이전 값을 비교한다는 점에서 Stack 자료구조를 사용한다는 사실은 눈치챘지만 풀이를 떠올리지 못해 결국 다른 코드를 찾아보았다.

 

https://girawhale.tistory.com/7

[프로그래머스] 주식가격(Stack) - JAVA

 

위 블로그를 참고하여 문제를 풀어 보았다.

인덱스가 곧 시간이라는 점을 활용해 Stack에 배열의 값이 아닌 인덱스를 담아 문제를 풀었다.

 

시간이 지날 때, 계속 이전 시간의 값을 peek() 하며 비교해주었고, 만약 가격이 떨어졌다면 해당 시간의 answr 배열에 이전 시간만큼 빼주면서 시간의 흐름을 저장하였다.

계산된 시간은 Stack에서 pop() 해주고 새로운 시간을 넣어준다.

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

 

 

시간이 모두 흐르고 Stack에는 끝까지 가격이 떨어지지 않은 인덱스가 남아있다.

Stack을 비우면서 나머지 시간까지 계산해준다.

 

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

 

 

 

전체 코드 (Java)

import java.util.*;

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()]) {
                answer[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        
        
        while (!stack.isEmpty()) {
            answer[stack.peek()] = prices.length - stack.pop() - 1;
        }
        
        return answer;
    }
}

 

 

후기

Stack에 배열의 값을 넣을 생각만 하였지 인덱스를 넣을 생각은 하지 못했다. 좀 더 넓게 생각하는 습관을 가져야겠다.