leetcode medium : 132 pattern

https://leetcode.com/problems/132-pattern/description/

132 Pattern - LeetCode

 

풀기 전

숫자 리스트가 주어졌을 때, 132 패턴이 있는지 찾는 문제다. 132 패턴은 말 그대로 인덱스 i,j,k를 임의로 선정했을 때 (i<j<k), list[i] < list[k] < list[j] 를 만족하는 것을 말한다. 1,3,2처럼 말이다.

상수 조건을 보니 n의 개수가 2 * 10^5다. O(N^2)의 알고리즘은 좀 위험해보이고 최소 O(N log N) 정도는 되어야 할 것 같다.

각 리스트 요소 값들은 -10^9~10^9로 범위가 매우 넓은데 크게 신경 쓸 필요는 없을것같다.

132 패턴은 비교적 단순한 패턴이고 리스트의 어느 숫자를 고르든 있는지 없는지 확인만 하면 되기 때문에 단순하게 원스캔으로 해결할 수 있어보인다. 대소를 비교해서 특정한 order를 가지는 숫자를 찾아야된다. 원스캔하면서 특정한 order에 맞는 숫자들을 기억할 수 있다? monotonic stack이 떠오른다.

132 패턴을 뒤집어서 생각해보자. 231 패턴이다. 2,3은 숫자가 증가하는 모습이다. 이때 2에 해당하는 숫자는 가급적 3이랑 차이가 나지 않고 클수록 좋다. 그래야 1로 고를 수 있는 숫자의 범위가 넓어지기 때문이다. 이를테면 5,10을 골랐으면 나머지 숫자는 5보다 작은 숫자를 골라야 한다. 15,16을 골랐으면 나머지 숫자는 15보다 작은 숫자를 찾으면 되므로 마지막 숫자 선택의 폭이 더 넓어진다.

그럼 monotonic stack에 숫자를 증가하는 패턴으로 넣으면 어떻게 될까? monotonic stack의 크기가 2 이상 되면 stack의 top이 3에 해당하는 숫자가 될수 있을거고 stack의 top으로부터 2번째 요소가 2에 해당하는 숫자가 될 수 있을 것이다. 새로 보게 되는 숫자가 1에 해당하는 숫자면 stack을 2번 pop시킬 수 있을 것이다. 하지만 이렇게 하면 문제가 있다. 2랑 3은 큰 숫자일수록 좋은데 이런 방식은 이를 보장하지 않는다. 예를 들어 [4,3,0,5,3]이라는 숫자를 만나면 4,5,3을 고르면 231 패턴이 된다. 하지만 monotonic stack에 increasing order로 숫자를 쌓으면 3을 만나자마자 4는 소멸되어 없어진다.

반대로 decreasing order로 생각해보자. 스택에서는 큰숫자부터 작은 숫자 순으로 숫자가 쌓일 것이다. 위의 예제 데이터에서 첨에 넣은 조금 큰 수인 4를 잃지 않고 5를 만날때까지 보관할 수 있다. 그리고 스택에 새로운 요소를 push하기 전에 가장 마지막에 pop된 요소는 스택의 새로운 요소보다 작으면서 가장 큰 수임이 보장된다. 스택의 새로운 요소가 3에 해당하는 숫자가 되는거고 가장 마지막에 pop된 요소가 2에 해당하는 숫자가 되는것이다. 이 2에 해당하는 숫자를 저장해놨다가 새 숫자를 스캔할 때 2보다 작은지 검사하기만 하면 2,3,1 패턴이 존재하는지 확인할수있다. 리스트를 거꾸로 스캔하면서 이 방식을 적용하면 1,3,2 패턴이 존재하는지 확인할 수 있다.

코드 설명

        n2 = float('-inf')
        stack = []

s2는 132패턴에서 2에 해당하는 숫자를 저장하는 변수다. 나중에 코드를 보면 알겠지만 얘보다 작은 수를 만나면 132패턴에서 1에 해당하는 숫자로 판단할 것이므로 -무한대로 초기화해놔야 버그가 발생하지 않는다.

stack은 모노토닉 스택이다.

for i in range(len(nums) - 1, -1, -1):
    if nums[i] < n2:
        return True

    while stack and nums[i] > stack[-1]:
        n2 = stack.pop()

    stack.append(nums[i])

231패턴을 거꾸로 탐지하기 위해 for문을 거꾸로 돌린다. range가 len(nums)-1부터 시작해 -1까지 -1스텝으로 간다.

if nums[i] < n2:
	return True

리스트를 거꾸로 스캔하면서 새로 보게되는 요소 nums[i]가 s2보다 작으면 stack의 top에 해당하는 요소가 s3고 nums[i]가 s1이 되어 132패턴이 완성된다. 리턴 True

while stack and nums[i] > stack[-1]:
    n2 = stack.pop()

stack.append(nums[i])

여타 모노토닉 스택의 코드랑 다를게 없다. 한 가지 차이점은 가장 최근에 pop한 요소를 s2에 저장한다는 것이다.

분석 및 피드백

리스트의 요소가 N개라고 치면, N개의 요소를 원스캔한다.

스택에 이것저것 넣고 뺀다고는 해도 결국 삽입 횟수는 N번이고 pop횟수는 N번 이하다.

그래서 시간복잡도는 O(N)이 된다.

1,3,2,1,2,3,4,5,..999,1000

이런 형태의 리스트를 만나면, 코드가 리스트를 거꾸로 스캔하면서 decreasing order로 monotonic stack을 유지하므로 스택에 N개 가까운 1000개의 요소가 쌓일 수 있다. 그래서 공간복잡도는 최대 O(N)이 된다.

풀 수 있는 방법중에 가장 깔끔하게 푼 거 같다. 더 최적화 할 필요는 없어보인다.

솔루션 학습

class Solution {
    public boolean find132pattern (int[] nums) {
        Stack <Integer> stack = new Stack ();
        int second = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums [i] < second)
                return true;
            while (!stack.isEmpty() && nums [i] > stack.peek ())
                second = stack.pop ();
            stack.push (nums [i]);
        }
        return false;
    }
}

다른 솔루션들도 내 솔루션과 방법엔 크게 차이가 없어보인다.