## 🌟 문제
[코딩테스트 연습 - 주식가격 \| 프로그래머스 스쿨](https://school.programmers.co.kr/learn/courses/30/lessons/42584)
각 시점의 주식 가격이 떨어지지 않은 기간을 구하는 문제이다.
## 🌟 풀이
가격이 떨어지는 시점을 만났을 때, 스택에 쌓여 있는 이전 데이터들을 역순으로 처리해서 답을 구하면 O(N)으로 해결할 수 있다.
처음에는 이렇게 풀었는데, 하나의 테스트 케이스에서 시간 초과가 발생했다.
```javascript
function solution(prices) {
const pricesData = prices.map((price, day) => ({price, day}));
const stack = [];
const answer = Array(prices.length).fill(0);
for (const {price, day} of pricesData) {
if (stack.length === 0) stack.push({price, day});
else {
while (stack.length !== 0) {
const top = stack[stack.length - 1];
if (top.price <= price) break;
stack.pop();
answer[top.day] = day - top.day;
}
stack.push({price, day});
}
}
for (const {price, day} of stack) {
answer[day] = prices.length - day - 1;
}
return answer;
}
```
알고리즘 자체는 O(N)으로 푸는게 맞았는데, 이리저리 자료구조를 바꿔보니 `pricesData`를 하나 더 만든 것이 원인이었다. 인덱스와 가격을 함께 묶어서 관리해야 할 것 같아서 객체 배열을 하나 더 만들었던 것인데, 이렇게 하니 배열 할당, `for...of` 구조분해 같이 불필요한 시간들이 더 쓰인 것이 문제였다.
prices가 어차피 인덱스가 유지되는 배열이기 때문에, 그냥 인덱스만 저장하는 것으로도 충분했다. 그래서 아래처럼 수정했고 통과할 수 있었다.
```javascript
function solution(prices) {
const stack = [];
const answer = Array(prices.length).fill(0);
for (let idx = 0; idx < prices.length; idx++) {
while (stack.length > 0 && prices[stack[stack.length - 1]] > prices[idx]) {
const top = stack.pop();
answer[top] = idx - top;
}
stack.push(idx);
}
while (stack.length > 0) {
const top = stack.pop();
answer[top] = prices.length - top - 1;
}
return answer;
}
```
~~이렇게 기준이 빡빡한게 실화라니...~~