기존에 Stack을 다룰 때, 값들을 Stack에 넣어서 사용하는 간단한 문제만 풀어보다가 index를 스택에 저장하여 사용하는 방식의 문제가 있어서 기록합니다.

✏️ 문제 설명

temperatures 배열의 각 원소에 대해 자신보다 큰 값이 나오는 Index 차이를 알아내어, 해당 값을 output 배열에 넣어 반환.

Approach 1. O(n^2) : Brute False

변수선언 `output[]`: 정답을 저장할 배열

1. `stack[]` : 순회한 값들을 저장할 배열
2. `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)

1. 변수선언
   `idx_stack[]` : output이 정해지지 않은 temperatures의 index를 저장한 배열
   `ouput[]` : 결과값을 저장할 배열
2. `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;
};

공유하고 싶었던 내용

1. ⭐ Stack을 다룰 때, index만을 다룰 수 있다는 유연함 ⭐
2. Monotonic 배열에서 while 문을 통한 배열 checking