【프로그래머스】 스택/큐 - 주식가격 (Java)

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

 

---

풀이

입력된 배열이 [1, 3, 2, 3, 1, 2, 3]이라 하자. 직접 풀면 다음과 같은 결과를 얻을 것이다.

1초: 끝까지 가격이 떨어지지 않는다.
2초: 1초 뒤에 가격이 떨어진다.
3초: 2초 뒤에 가격이 떨어진다.
4초: 1초 뒤에 가격이 떨어진다.
5초: 끝까지 가격이 떨어지지 않는다.
6초: 끝까지 가격이 떨어지지 않는다.
7초: 0초 동안 가격이 떨어지지 않는다.

결과: [6, 1, 2, 1, 2, 1, 0]

 

정답을 저장할 크기가 prices.length와 같은 정수 배열(이하 answer)과 초를 저장할 스택(이하 stack)을 사용한다.

prices의 각 인덱스 i에 대해 i초 때의 가격을 stack에 저장된 이전 시점들과 비교하여 가격이 떨어졌는지 확인할 것이다.

가격이 떨어진 시점을 발견하면 즉시 정답을 계산하여 answer의 해당하는 위치에 저장한다.

i = 0, stack = []

비교할 대상이 없으므로 stack에 0을 push하고 다음 단계로 넘어간다.

i = 1, stack = [0]

1초 때의 가격과 stack.peek = 0초 때의 가격을 비교한다.
prices[1] = 3 > 1 = prices[0]이므로 0초 때의 가격은 유지되고 있다.

이후 시점에서 1초 때의 가격을 사용하기 위해 stack에 1을 push한다.

i = 2, stack = [0, 1]

2초 때의 가격과 stack.peek = 1초 때의 가격을 비교한다.
prices[2] = 2 < 3 = prices[1]이므로 1초 때의 가격이 떨어졌다.
가격이 유지된 시간은 현재 시각(i) - 해당 시각(1) = 1초이며 이를 answer[1]에 저장한다.
1초는 정답을 이미 구해 더 이상 필요하지 않으므로 stack에서 pop한다.

이어서 2초 때의 가격과 stack.peek = 0초 때의 가격을 비교한다.
prices[2] = 2 > 1 = prices[0]이므로 0초 때 가격은 유지되고 있다.

이전과 마찬가지로 stack에 2를 push한다.

i = 3, stack = [0, 2]

3초 때의 가격과 stack.peek = 2초 때의 가격을 비교한다.
prices[3] = 3 > 2 = prices[2]이므로 2초 때의 가격은 유지되고 있다.

stack은 0~2초까지 가격이 유지되고 있다는 것을 의미한다.
따라서 3초 때의 가격과 0초 때의 가격을 직접 비교하지 않아도 가격이 유지되고 있다는 것을 알 수 있다.

stack에 3을 push한다.

i = 4, stack = [0, 2, 3]

4초 때의 가격과 stack.peek = 3초 때의 가격을 비교한다.
prices[4] = 1 < 3 = prices[3]이므로 3초 때의 가격이 떨어졌다.
가격이 유지된 시간은 i - stack.peek = 4 - 3 = 1초이며 이를 answer[3]에 저장한다.
stack에서 3을 pop한다.

이어서 stack.peek = 2초 때의 가격과도 비교한다.
prices[4] = 1 < 2 = prices[2]이므로 2초 때의 가격이 떨어졌다.
가격이 유지된 시간은 i - stack.peek = 4 - 2 = 2초이며 이를 answer[2]에 저장한다.
stack에서 2를 pop한다.

이어서 stack.peek = 0초 때의 가격과도 비교한다.
prices[4] = 1 = prices[0]이므로 0초 때의 가격은 유지되고 있다.

stack에 4를 push한다.

i = 5, stack = [0, 4]

5초 때의 가격과 stack.peek = 4초 때의 가격을 비교한다.
prices[5] = 2 > 1 = prices[4]이므로 4초 때의 가격은 유지되고 있다.

stack은 0~4초까지 가격이 유지되고 있다는 것을 의미한다.
따라서 5초 때의 가격와 0초 때의 가격을 직접 비교하지 않아도 가격이 유지되고 있다는 것을 알 수 있다.

stack에 5를 push한다.

i = 6, stack = [0, 4, 5]

6초 때의 가격과 stack.peek = 5초 때의 가격을 비교한다.
prices[6] = 3 > 2 = prices[5]이므로 5초 때의 가격은 유지되고 있다.

stack은 각각 0초와 4초에서 5초까지 가격이 유지된다는 것을 의미한다.
따라서 나머지 시점은 직접 비교하지 않아도 가격이 유지되고 있다는 것을 알 수 있다.

stack에 6을 push한다.

 

반복 작업을 거치고 난 뒤 stack의 각 요소는 가격이 끝까지 유지된 시점을 의미한다.

각 시점 time에 대한 가격 유지 시간은 prices.length - 1 - time으로 계산할 수 있다.

이를 answer의 해당하는 위치에 저장하면 answer는 [6, 1, 2, 1, 2, 1, 0]이 된다.

 

코드

import java.util.Stack;

public int[] solution(int[] prices) {
    int n = prices.length;
    int[] answer = new int[n];
    Stack<Integer> stack = new Stack<>();

    // 0초부터 n - 1초까지 반복
    for (int i = 0; i < n; i++) {
        // 가격이 더 높은 이전 시점을 찾을 경우
        while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
            // 스택에서 pop하고 유지 시간을 계산하여 배열에 저장
            answer[stack.peek()] = i - stack.pop();
        }

        // 이후 시점에서 비교하기 위해 현재 시점을 스택에 push
        stack.push(i);
    }

    // 끝까지 가격이 유지된 시점에 대한 유지 시간을 계산하여 배열에 저장
    for (int time : stack) {
        answer[time] = n - 1 - time;
    }

    return answer;
}