132 패턴 문제의 이해

배열 nums가 주어졌을 때, i < j < k 인덱스 순서를 만족하면서 nums[i] < nums[k] < nums[j] 관계를 가지는 패턴이 존재하는지 확인하는 문제입니다. 즉, 첫 번째 숫자가 가장 작고, 두 번째 숫자가 가장 크며, 세 번째 숫자가 그 중간 값을 가지는 부분 수열을 찾아야 합니다.

1. 브루트 포스(Brute Force) 방식

가장 직관적인 방법은 세 개의 인덱스를 모두 순회하며 조건을 확인하는 것입니다. 중첩된 세 개의 루프를 사용하여 모든 조합을 검사합니다.

func is132PatternNaive(data []int) bool {
    size := len(data)
    if size < 3 {
        return false
    }

    for i := 0; i < size; i++ {
        for j := i + 1; j < size; j++ {
            for k := j + 1; k < size; k++ {
                if data[i] < data[k] && data[k] < data[j] {
                    return true
                }
            }
        }
    }
    return false
}

이 방식의 시간 복잡도는 O(n³)입니다. 데이터의 크기가 커질수록 처리 속도가 급격히 저하되어 실제 환경이나 대량의 테스트 케이스에서는 타임아웃(Timeout)이 발생할 가능성이 매우 높습니다.

2. 모노토닉 스택을 이용한 최적화 알고리즘

브루트 포스의 한계를 극복하기 위해 모노토닉 스택(Monotonic Stack)을 활용하여 O(n) 시간에 해결할 수 있습니다. 132 패턴에서 '3'은 가장 큰 값, '2'는 중간 값, '1'은 가장 작은 값임을 기억해야 합니다.

이 최적화 기법의 핵심 로직은 배열을 역순(뒤에서부터 앞쪽으로)으로 훑는 것입니다.

• 스택(Stack): '3'(가장 큰 값)의 후보들을 보관합니다.
• secondValue (2의 역할): 지금까지 발견된 '3'보다 작으면서, 그중 가장 큰 값을 유지합니다. 스택에서 팝(pop)된 값이 이 변수에 할당됩니다.
• 현재 요소 (1의 역할): 역순 순회 중 현재 보고 있는 숫자가 secondValue보다 작다면, nums[i] < nums[k] 조건을 만족하는 것이므로 패턴을 찾은 것으로 간주합니다.

import "math"

func find132PatternOptimized(nums []int) bool {
    n := len(nums)
    if n < 3 {
        return false
    }

    // '2'에 해당하는 값을 저장 (nums[k])
    // 패턴 nums[i] < nums[k] < nums[j] 에서 nums[k]의 최대값을 추적
    lastValidK := math.MinInt64
    stack := []int{}

    // 배열을 뒤에서부터 순회 (j와 k를 먼저 결정하는 방식)
    for i := n - 1; i >= 0; i-- {
        // 현재 숫자가 '1'의 후보가 될 수 있는지 확인
        if nums[i] < lastValidK {
            return true
        }

        // 현재 숫자가 스택의 상단 값보다 크면, 
        // 현재 숫자를 '3'으로 보고 스택의 값을 '2'로 업데이트
        for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
            lastValidK = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }

        // 현재 숫자를 '3'의 후보로 스택에 추가
        stack = append(stack, nums[i])
    }

    return false
}

동작 원리 분석

배열을 뒤에서부터 읽으면서 스택을 단조 감소 상태로 유지합니다. 새로운 숫자가 스택의 top보다 크다면, 기존 스택에 있던 숫자들은 현재 숫자보다 작은 '2'의 후보가 됩니다. 이들 중 가장 큰 값을 lastValidK로 설정함으로써, 이후에 더 작은 값('1')이 나타나기만 하면 바로 패턴이 완성됩니다.

이 알고리즘은 배열을 한 번 순회하고, 각 요소가 스택에 한 번 들어갔다 나오므로 전체 시간 복잡도는 O(n)이며, 공간 복잡도는 스택을 위한 O(n)을 사용합니다.