Leetcode Java 132 Pattern

문제

Link

코드

class Solution {

  public boolean find132pattern(int[] nums) {
    int length = nums.length;
    int index = length;
    int max = Integer.MIN_VALUE;
    for (int idx = length - 1; idx >= 0; idx--) {
      if (nums[idx] < max) {
        return true;
      }
      while (index < length && nums[idx] > nums[index]) {
        max = nums[index++];
      }
      nums[--index] = nums[idx];
    }
    return false;
  }

}

결과

Link

설명

1. 배열 nums 내 132 패턴을 찾는 문제이다.
   • 132 패턴은, i < j < k의 관계에서 nuns[i] < nums[k] < nums[j]의 관계가 성립하는 패턴이다.
2. 문제 풀이에 필요한 변수를 정의한다.
   • length는 nums의 길이를 저장하기 위한 변수로, nums의 길이로 초기화한다.
   • index는 nums를 역순으로 탐색하기 위한 변수로, length로 초기화한다.
   • max는 가장 큰 수를 저장하기 위한 변수로, 정수의 가장 작은 값으로 초기화한다.
3. $length - 1$부터 0까지 반복하여 아래를 수행한다.
   • nums의 idx 번째 값이 max보다 작으면 132 패턴을 만족하므로, true를 주어진 문제의 결과로 반환한다.
   • index가 length보다 작고 nums의 idx번째 값이 nums의 index번째 값보다 클 경우 max에 nums의 index번째 값을 넣고, index를 증가시킨다.
   • nums의 $index - 1$ 위치에 nums의 idx 번째 값을 넣고 반복을 계속 수행한다.
4. 반복이 완료되면 132 패턴을 만족하는 수가 없으므로, false를 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.