Leetcode 456. 132 Pattern

문제

Given an array of n integers nums, 
a 132 pattern is a subsequence of three integers nums[i], 
nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

정수 배열이 주어집니다.
index는 i < j < k 인데, 배열 nums에 대해 nums[i] < nums[k] < nums[j] 인 패턴이 존재하는지를 리턴하세요.
예를 들자면 [1, 3, 2] 가 있습니다.

예시

Input: nums = [1,2,3,4]
Output: false
Explanation: 위와 같은 패턴이 존재 하지 않음.

제한

• $n == nums.length$
• $1 <= n <= 2 * 10^5$
• $-10^9 <= nums[i] <= 10^9$

풀이법

• 코드를 먼저 두고 설명을 이어 나가겠습니다.

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stck: List[int] = []
        m: int = -(10 ** 9 + 1)

        for index in range(len(nums) - 1, -1, -1):
            if nums[index] < m:
                return True
            while stck and stck[-1] < nums[index]:
                m = stck[-1]
                stck.pop()
            stck.append(nums[index])

        return False

1. 자료구조 선언

• 스택과 정수 하나가 사용됩니다.
  • 스택 : 값을 트래킹 하기 위해 사용
  • 정수 : 패턴에 들어갈 세번째 숫자를 저장하기 위해 사용

        stck: List[int] = []
        m: int = -(10 ** 9 + 1)

2. For loop

• for loop는 뒤에서부터 맨 앞으로 진행됩니다.
• 패턴의 세번째 값으로 지정된 값보다 작다면 132 패턴이 완성된 것이므로 True를 리턴합니다.
• 이 세번째 값을 정하기 위해선 아래와 같은 방식을 사용합니다.
  • 스택이 비어있지 않고,
    스택의 top보다 현재 순회중인 값이 크다면
    현재 순회중인 값이 두번째 값이 됩니다.
  • 이를 만족하는 값이 발견 될 때까지 찾다가 찾으면 이를 세번째 값으로 정하고 스택에서 pop 합니다.
  • 만약 이를 찾지 못할시 어차피 세번째 숫자는 가능한 최소의 수로 초기 설정이 되어있어 맨 앞의 조건을 통과하지 못해 괜찮습니다.
• 세번째 값을 이용하되, 스택에는 다시 순회중인 값을 넣는데, 이는 현재 값이 세번째 값으로 사용될수 있기 때문입니다.

시간복잡도

• 순차적으로 순회, O(n) 의 시간복잡도를 가집니다.