LeetCode 456. 132 Pattern (132 패턴)

문제 링크

제한시간: 15분

문제 설명

정수 배열 nums가 주어졌을 때, 132 패턴을 찾아 반환한다.

132 패턴이란?

132 패턴이란 세 개의 정수 nums[i], nums[j], nums[k]로 이루어진 부분 수열로, 다음 두 조건을 모두 만족한다.

i < j < k
nums[i] < nums[k] < nums[j]

이러한 패턴이 존재하면 true를, 그렇지 않으면 false를 반환하는 문제다.

제약 조건:

시간 복잡도: O(n)

1 <= n <= 2 \* 10^5
-10^9 <= nums[i] <= 10^9

풀이

이 문제의 해설과 오답 사고 과정을 보면서, 배열 순회 방향을 익숙한 도구로 삼아야지 싶었다. 왠지 순회를 0부터 시작하려는 습관이 있는 것 같다.
풀이는 다음 링크를 참고했다. (링크)

스택을 뒤부터 순회하면서 현재 값(nums[i])이 스택 맨 위 값보다 클 때, 스택에서 값을 꺼내 thirdNum에 저장한다.
- 이렇게 하면 스택에 남아있는 값은 항상 thirdNum보다 작은 값이 된다.
반복문 내부에서 true를, 외부에서 무조건 false를 반환한다.
i가 0이 되기 전에 미리 true를 반환하여 반복을 줄일 수 있고, 마지막에 조건을 확인하는 것보다 빠르다.
반복문 첫 사이클에서만 nums[i] < thirdNum === false를 만들기 위해 -Infinity를 활용하는 게 꽤 인상적이다.

var find132pattern = function (nums) {
  const N = nums.length;
  // 스택을 사용하여 nums[j] 후보들을 저장
  const stack = [];
  // nums[k]가 될 후보 값 (nums[j]보다 작은 값)
  let thirdNum = -Infinity; // 뒤에 있는 숫자가 항상 크다. 아래 노트 참조

  // 배열을 뒤에서부터 순회
  for (let i = N - 1; i >= 0; i--) {
    // 현재 값이 thirdNum(nums[k])보다 작으면 132 패턴 발견
    if (nums[i] < thirdNum) {
      return true;
    }

    // 스택이 비어있지 않고, 현재 값이 스택의 맨 위 값보다 크면
    // 스택에서 값을 꺼내 thirdNum 업데이트
    while (stack.length  && nums[i] > stack[stack.length - 1]) {
      thirdNum = stack.pop();
    }

    // 현재 값을 스택에 추가
    stack.push(nums[i]);
  }

  return false;
};

JavaScript에서 Infinity와 -Infinity의 차이

Infinity: 양의 무한대. 모든 숫자보다 큰 값
-Infinity: 음의 무한대. 모든 숫자보다 작은 값

이 문제에서는 뒤에 있는 숫자가 항상 커야한다. 따라서 초기값을 -Infinity로 설정한다.

오답 사고 과정

3개의 포인터를 움직이며 조건을 확인한다
포인터를 최대한 움직인 후, 인덱스와 값이 모두 조건에 맞는 지 확인한다.

제한 시간이 끝날 때 쯤, 내가 떠올린 방법은 포인터의 최소/최장 길이를 찾을 때 쓰는 게 아닐까 싶었다.
그제서야 문제 접근을 잘못했다는 사실을 깨달았다. 조건에 맞지 않아 포인터가 전혀 움직이지 않아도 true가 반환될 수 있다.

var find132pattern = function (nums) {
  if (nums.length < 1) return false;
  const N = nums.length;
  let start = 0,
    mid = Math.floor(N / 2),
    end = N - 1;

  function getCorrect(cur, target) {
    return cur < target && nums[cur] < nums[target];
  }

  while (getCorrect(start, mid)) {
    start++; // 이 안에 포인터 이동 방법을 잘 몰랐다.
  }

  while (getCorrect(start, mid)) {
    mid--; // 마찬가지로 이 안에 포인터 이동을 잘 몰랐다.
  }

  while (getCorrect(mid, end)) {
    end--;
  }
  // 포인터 이동이 전혀 없이 조건에 맞거나 틀릴 수 있다.
  return (
    start < mid && mid < end && nums[start] < nums[mid] && nums[mid] < nums[end]
  );
};