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

이 문제는 프로그래머스 LV2에 해당하는 코딩테스트 문제다.

'스택/큐'에 대한 개념이 아직 잘 잡혀있지 않아서 나는 문제를 처음 보고 이중for문을 사용하는 방식으로 접근했다.

아래 코드는 이중for문을 활용한 방식이다.

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

 

 

그러나 이 로직의 시간복잡도는 O(n²) 이기 때문에 스택을 활용한 방식으로 접근하는 것이 더 좋다.

이중 for문은 각 원소마다 뒤의 모든 원소를 탐색한다. 따라서 이미 확인했던 원소를 또 확인하는 일이 반복된다.

반면 스택을 사용하면 아직 가격이 떨어지지 않은 인덱스만 관리하면 된다.

여기서 가장 중요한 점은 가격이 아니라 인덱스를 저장한다는 것이다.

문제에서 필요한 것은 가격 자체가 아니라 몇 초 동안 가격이 유지되었는지이다.

몇 초가 유지되었는지는

현재 인덱스 - 이전 인덱스

로 계산할 수 있다.

따라서 가격만 저장해서는 몇 초가 지났는지 계산할 수 없으며, 반드시 인덱스를 저장해야 한다.

가격은 필요할 때마다

prices[index]

로 언제든지 확인할 수 있다.

 

 

예제

prices = [1, 2, 3, 2, 3]

스택은 비어있는 상태다.

 

i=0

현재 가격은 1이다.

스택이 비어 있으므로 비교할 대상이 없다.

따라서 현재 인덱스(0)를 스택에 넣는다.

 

i=1

현재 가격은 2이다.

스택의 맨 위에는 인덱스 0이 있다.

가격을 비교하면 현재 가격이 더 크므로 아직 가격이 떨어지지 않았다.

따라서 인덱스 1을 스택에 넣는다.

 

i=2

현재 가격은 3이다.

스택의 맨 위는 인덱스 1이다.

비교하면 가격이 떨어지지 않았다.

인덱스 2를 스택에 넣는다.

 

i=3

현재 가격은 2이다.

스택의 맨 위는 인덱스 2이다.

비교하면 가격이 떨어졌다.

이제 인덱스 2의 답을 계산할 수 있다.

 

스택에서 꺼내면

index = 2

현재 위치는

i = 3

이므로

3 - 2 = 1초

가격이 유지되었다.

 

따라서

answer[2] = 1;

이 된다.

 

이후 스택의 다음 원소를 확인한다.

현재 스택의 맨 위는 인덱스 1이다.

가격이 떨어진 것이 아니므로 반복문을 종료하고 현재 인덱스(3)을 스택에 넣는다.

stack = [3, 1, 0]

 

i=4

현재 가격은 3이다.

스택의 맨 위는 인덱스 3이다.

가격이 떨어지지 않았으므로 인덱스 4를 스택에 넣는다.

stack = [4, 3, 1, 0]

 

모든 탐색이 끝났다.

탐색이 끝났는데도 스택에 원소가 남아 있다는 것은 끝까지 가격이 한 번도 떨어지지 않았다는 의미이다.

따라서 남아있는 인덱스들은

prices.length - 1 - index

만큼 가격이 유지된 것이다.

 

이 문제는 가격을 저장하는 문제가 아니라, 아직 가격이 떨어지지 않은 인덱스를 관리하는 문제이다.

 

 

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < prices.length; i++) {

            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                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;
    }
}

최종 코드다.