기존에 Stack을 다룰 때, 값들을 Stack에 넣어서 사용하는 간단한 문제만 풀어보다가 index를 스택에 저장하여 사용하는 방식의 문제가 있어서 기록합니다.
✏️ 문제 설명
temperatures 배열의 각 원소에 대해 자신보다 큰 값이 나오는 Index 차이를 알아내어, 해당 값을 output 배열에 넣어 반환.
Approach 1. O(n^2) : Brute False
변수선언 `output[]`: 정답을 저장할 배열
- `stack[]` : 순회한 값들을 저장할 배열
- `temperatures[]` 의 뒤에서부터 순회한다.
- 각 temperature에 대해 스택의 앞에서 부터 순회하며, temperature보다 큰 값을 구할 때 까지 count 한다.
- 큰 값이 나오면, 해당 값을 `ouput[]`의 맨 앞에 추가한다.
var dailyTemperatures1 = function (temperatures) {
const output = [];
let stack = [];
while (temperatures.length > 0) {
const target = temperatures.pop();
let cnt = 0;
let flag = false;
for (const num of stack) {
if (num <= target) cnt++;
else {
cnt++;
flag = true;
break;
}
}
stack.unshift(target);
if (flag) {
output.unshift(cnt);
} else {
output.unshift(0);
}
}
return output;
};
Time Out Error!
n ≤ 10^5 이므로, 10^4 * 10^4 = 1초 원칙에 의거 시간이 부족함.
Approach 2. O(n) : Stack (Monotonic Decreasing)
- 변수선언
`idx_stack[]` : output이 정해지지 않은 temperatures의 index를 저장한 배열
`ouput[]` : 결과값을 저장할 배열 - `temperatures []`순회
각 temperature에 대해, `idx_stack[]` 의 뒤에서 부터, 자신보다 값이 작은게 오면, pop() 하여 output에 index 차이를 저장
var dailyTemperatures = function (temperatures) {
const len = temperatures.length;
const idx_stack = [];
const output = new Array(len).fill(0);
for (let i = 0; i < temperatures.length; i++) {
const target = temperatures[i];
while (
idx_stack.length > 0 &&
target > temperatures[idx_stack[idx_stack.length - 1]]
) {
const idx = idx_stack.pop();
output[idx] = i - idx;
}
idx_stack.push(i);
}
return output;
};
공유하고 싶었던 내용
- ⭐ Stack을 다룰 때, index만을 다룰 수 있다는 유연함 ⭐
- Monotonic 배열에서 while 문을 통한 배열 checking