[leetcode] 739. Daily Temperatures

hansol yang

·

Follow

3 min read

·

Jul 23, 2023

--

Share

• brute force
• 비교해서 보다 큰 수를 찾고, 다 돌아봤는데도 없으면 0을 담아주면 된다.

function dailyTemperatures(temperatures: number[]): number[] {
  const res: number[] = [];

  for (let i = 0; i < temperatures.length; i++) {
    for (let j = i + 1; j < temperatures.length; j++) {
      if (temperatures[i] < temperatures[j]) {
        res.push(j - i);
        break;
      }
    }

    if (res.length === i) {
      res.push(0);
    }
  }

  return res;
};

• stack 활용
• 배열을 순회하면서 큰 값을 만나는 순간 즉 변곡점을 기다린다. 변곡점 값을 만나기 전까지는 stack 에 담아둔다. 그러다가 변곡점을 만나면 변곡점과 이전의 stack 에 쌓아뒀던 값들 사이의 차이를 구한다. 이 때 날짜 차이가 필요한 것이고, 정답 배열에도 원하는 포지션을 값을 넣기 위해 stack 에는 index 를 담아둔다. 변곡점을 만나면 stack 을 확인해가면서 stack 의 값이 더 작다면 pop 해서 꺼내고 변곡점과의 차이를 정답 배열에 담는다. 그렇게 처리할 수 있는 만큼 처리하고 현재 값도 stack 에 담는다. 이런식의 진행으로 stack 은 자연스레 큰 값부터 작은 값 까지의 순서로 정렬된다. 그리고 변곡점이 stack 의 있는 모든 값보다 크다면 stack 은 비워지는 식이다. 이렇게 끝까지 다 돌았는데도 정답을 못찾은 값들은 0 을 채워주면 된다.
• 이 방법은 책을 살짝 커닝해서 풀었다. 이런식으로 문제에 접근하는 사고방식을 떠올리는게 쉽지가 않다.
• neetcode 설명 보면 역시 도움이 된다.

const dailyTemperatures = (temperatures: number[]) => {
  let res = Array.from<number>({ length: temperatures.length }).fill(0);
  let stack: number[] = [];

  temperatures.forEach((v, i) => {
    while (stack.length && v > temperatures[stack[stack.length - 1]]) {
      let last = stack.pop();
      if (last !== undefined) {
        res[last] = i - last;
      }
    }
    stack.push(i);
  });

  return res;
};