Programmers | Level 2 | 주식가격
Programmers | Level 2 | 주식가격
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Stack
Description
주식가격이 초 단위로 기록된 배열 prices가 주어집니다. 이 배열에서 각 주식가격이 떨어지지 않은 기간(초 단위)을 계산하여 배열로 반환하는 것이 목표입니다. 예를 들어, 주식가격이 [1, 2, 3, 2, 3]와 같다면, 각 가격이 떨어지지 않은 기간은 [4, 3, 1, 1, 0]이 됩니다.
Constraints
prices배열의 길이는 2 이상 100,000 이하입니다.- 주식가격은 1 이상 10,000 이하의 자연수로 구성됩니다.
Examples
| prices | return |
|---|---|
[1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
Solutions
Code
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
int n = prices.length;
int[] answer = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
int j = stack.pop();
answer[j] = i - j;
}
stack.push(i);
}
while (!stack.isEmpty()) {
int j = stack.pop();
answer[j] = n - 1 - j;
}
return answer;
}
}
Approaches
이 문제는 주식 가격이 떨어지지 않은 기간을 효율적으로 계산하기 위해 스택(Stack) 자료구조를 사용한 접근법을 활용할 수 있습니다. 스택은 주식 가격의 인덱스를 저장하며, 가격이 하락할 때마다 스택에서 이전의 높은 가격 인덱스를 꺼내 해당 주식 가격이 유지된 기간을 계산합니다. 이 접근법을 통해 각 주식 가격이 언제 하락하는지를 추적하여 빠르게 결과를 도출할 수 있으며, 아래에서 이 과정을 단계별로 살펴보겠습니다.
1. 기본 데이터 및 스택 구조 초기화
주어진 주식 가격 배열 prices[]를 처리하기 위해 필요한 기본 데이터를 초기화합니다. 여기에는 각 주식 가격이 얼마나 오랜 기간 동안 유지되었는지를 기록할 answer[] 배열과, 주식 가격의 하락 시점을 추적하기 위한 스택이 포함됩니다. 이 단계에서는 이러한 기본 데이터를 설정하고, 이후의 계산을 위한 준비 작업을 수행합니다.
int n = prices.length;
int[] answer = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
stack: 주식 가격이 떨어지지 않은 시점들의 인덱스를 저장하는 데 사용됩니다. Java의Deque<T>를 활용하여 효율적인 삽입 및 삭제가 가능합니다.answer[]: 각 주식 가격이 유지된 기간을 저장하는 배열입니다. 각 인덱스에 해당하는 값은 그 시점부터 가격이 떨어질 때까지의 기간을 나타냅니다.
2. 주식 가격 하락 시점에 대한 기간 계산
현재 시점의 주식 가격이 스택에 저장된 이전 시점의 가격보다 낮다면, 스택에서 해당 시점의 가격을 꺼내어 유지된 기간을 계산하고, answer[] 배열에 저장합니다. 그렇지 않다면, 현재 시점의 인덱스를 스택에 추가합니다.
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
int j = stack.pop(); // 가격 하락 시점에 대한 유지 기간 계산
answer[j] = i - j; // 유지된 기간 저장
}
stack.push(i); // 현재 인덱스를 스택에 추가
}
- 가격 하락 시점 탐색: 현재 가격
prices[i]이 스택에 저장된 이전 가격prices[stack.peek()]보다 낮아지면, 해당 시점까지의 유지된 기간을 계산하여answer[]배열에 저장합니다. - 현재 시점 인덱스 추가: 가격이 하락하지 않는 경우, 현재 시점의 인덱스를 스택에 추가하여 이후의 비교를 위해 보관합니다.
아래는 주식 가격 [1, 2, 3, 2, 3]의 처리 과정을 단계별로 나열한 것입니다.
| 반복 단계 | 현재 시점 | 현재 가격 | 스택 상태 | 유지된 기간 상태 |
|---|---|---|---|---|
| 1 | 0 | 1 | [0] | [0, 0, 0, 0, 0] |
| 2 | 1 | 2 | [0, 1] | [0, 0, 0, 0, 0] |
| 3 | 2 | 3 | [0, 1, 2] | [0, 0, 0, 0, 0] |
| 4 | 3 | 2 | [0, 1, 3] | [0, 0, 1, 0, 0] |
| 5 | 4 | 3 | [0, 1, 3, 4] | [0, 0, 1, 0, 0] |
이 단계를 통해 주식 가격이 떨어진 시점에서의 기간을 효율적으로 계산할 수 있습니다. 결과적으로 스택에는 [0, 1, 3, 4]의 인덱스가 남게 되며, 이는 끝까지 가격이 떨어지지 않은 주식들을 나타냅니다.
3. 끝까지 가격이 떨어지지 않은 주식에 대한 처리
반복문이 종료된 후에도 스택에 남아 있는 시점들이 있다면, 이는 끝까지 가격이 떨어지지 않은 경우입니다. 이때는 남은 각 시점의 가격이 유지된 기간을 배열 끝까지로 계산합니다.
// 남은 시점의 기간 계산
while (!stack.isEmpty()) {
int j = stack.pop(); // 스택에서 남아 있는 시점 꺼내기
int duration = (n - 1) - j; // 배열의 끝까지 유지된 기간 계산
answer[j] = duration; // 해당 시점에 결과 저장
}
- 스택에 남아 있는 각 시점은 해당 주식 가격이 끝까지 하락하지 않은 경우를 의미합니다. 이때, 주식 가격이 유지된 기간은
prices[]배열의 마지막 인덱스에서 해당 시점의 인덱스stack.pop()을 뺀 값으로 계산됩니다. 이렇게 계산된 유지 기간은answer[]배열의 해당 위치에 저장됩니다. 예를 들어, 배열의 마지막 인덱스가 4일 때, 스택에 남아 있는 시점의 인덱스가 1이라면, 이 주식의 가격이 3초 동안 유지되었음을 의미합니다.
2단계 과정이 끝난 후 스택에 남아있던 [0, 1, 3, 4] 요소들은 이번 단계를 거치면서 answer[] 배열은 아래와 같이 갱신됩니다.
| 스택 처리 단계 | 현재 시점 | 현재 가격 | 스택 상태 | 유지 기간 | 유지된 기간 상태 |
|---|---|---|---|---|---|
| 1 | 4 | 3 | [0, 1, 3] | 0 = (5 - 1) - 4 | [0, 0, 1, 0, 0] |
| 2 | 3 | 2 | [0, 1] | 1 = (5 - 1) - 3 | [0, 0, 1, 1, 0] |
| 3 | 1 | 2 | [0] | 3 = (5 - 1) - 1 | [0, 3, 1, 1, 0] |
| 4 | 0 | 1 | [] | 4 = (5 - 1) - 0 | [4, 3, 1, 1, 0] |
이 단계에서, 주식 가격이 끝까지 떨어지지 않았던 시점들이 모두 처리되었습니다. 마지막에 남아 있는 스택의 인덱스들을 처리하여, answer[] 배열을 최종적으로 완성하게 됩니다.
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(n)
이 알고리즘의 시간 복잡도는 O(n)입니다. 각 주식 가격이 스택에 한 번 추가되고, 한 번 제거되기 때문에 배열의 각 요소가 최대 두 번만 처리됩니다. 공간 복잡도는 O(n)으로, 최악의 경우 스택에 모든 요소가 한 번에 저장될 수 있습니다.
현재 프로그래머스에서는 아래와 같이 이중 반복문을 활용한 방식도 테스트를 통과하고 있습니다:
import java.util.*;
class Solution {
public int[] solution(int[] prices) {
int n = prices.length;
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
answer[i]++;
if (prices[i] > prices[j]) break;
}
}
return answer;
}
}
처음에는 이중 반복문을 사용한 방식이 떠올라, 설마 하는 마음으로 제출했는데 의외로 통과했습니다. 그러나 이 방법은 O(n^2) 시간 복잡도를 가지며, 대규모 입력에 대해 비효율적일 수 있습니다. 이는 최악의 상황을 충분히 고려하지 않은 테스트 케이스가 누락되었기 때문일 수 있으며, 언젠가 추가될 가능성이 있습니다.
문제의 의도는 스택 자료구조를 활용한 최적화를 요구하는 것으로 보입니다. 스택을 활용한 방식이 이중 반복문보다 효율적이고 안정적이며, 대규모 입력에서도 일관된 성능을 보장합니다.
- Algorithm
- Stack