문제 개요
n개의 정수로 이루어진 수열 a₁, a₂, ..., aₙ이 주어졌을 때, 132 패턴은 인덱스 조건 i < j < k를 만족하면서 값의 조건 aᵢ < aₖ < aⱼ를 만족하는 부분 수열 aᵢ, aⱼ, aₖ를 의미합니다. 즉, 가장 작은 값, 가장 큰 값, 그리고 그 사이에 있는 값의 순서로 배치된 부분 수열을 찾아야 합니다.
우리의 목표는 n개의 숫자 목록을 입력으로 받아 이 목록 안에 132 패턴이 존재하는지 확인하는 알고리즘을 설계하는 것입니다.
예를 들어 입력이 [-1, 3, 2, 0]이라면 출력은 true입니다. 이 배열에는 [-1, 3, 2], [-1, 3, 0], [-1, 2, 0]이라는 세 가지 132 패턴이 존재하기 때문입니다.
해결 전략
이 문제는 최솟값 누적 배열과 스택을 함께 사용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
먼저 각 위치까지의 최솟값을 저장하는 배열 minVals를 만듭니다. minVals[i]는 인덱스 0부터 i까지 원소 중 가장 작은 값을 의미하며, 이것이 잠재적인 '1' 후보가 됩니다.
그다음 배열을 오른쪽에서 왼쪽으로 순회하면서 스택을 관리합니다. 스택에는 현재 위치 오른쪽에 있는 값들이 저장되며, 이 값들은 잠재적인 '2' 또는 '3' 역할을 할 수 있습니다.
순회 과정에서 현재 위치 왼쪽까지의 최솟값(minVal)보다 작거나 같은 스택의 원소는 모두 제거합니다. 이렇게 하면 스택에는 minVal보다 큰 값만 남게 되는데, 스택의 맨 위 값이 '3' 후보이고 현재 값(curr)이 '2' 후보가 됩니다.
스택이 비어 있지 않고 스택의 맨 위 값이 현재 값보다 작다면, minVal < 스택 맨 위 값 < curr 관계가 성립하므로 132 패턴이 존재한다는 뜻입니다. 이때 true를 반환합니다.
단계별 알고리즘
n := nums의 크기로 설정하고, n이 0이면 false를 반환합니다.
크기가 n인 배열 minVals를 정의하고, minVals[0] := nums[0]으로 초기화합니다.
i를 1부터 n − 1까지 반복하면서 minVals[i] := min(minVals[i − 1], nums[i])로 갱신합니다.
정수형 스택 st를 생성합니다.
i를 n − 1부터 1까지 역순으로 반복합니다.
minVal := minVals[i − 1]
curr := nums[i]
스택이 비어 있지 않고 스택의 맨 위 값이 minVal 이하인 동안 계속 pop합니다.
스택이 비어 있지 않고 스택의 맨 위 값이 curr보다 작으면 true를 반환합니다.
nums[i]를 스택에 push합니다.
반복문이 끝나면 false를 반환합니다.
C++ 구현 예제
다음 구현 코드를 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int n = nums.size();
if(!n) return false;
vector <int> minVals(n);
minVals[0] = nums[0];
for(int i = 1; i < n; i++){
minVals[i] = min(minVals[i - 1], nums[i]);
}
stack <int> s;
for(int i = n - 1; i > 0; i--){
int minVal = minVals[i - 1];
int curr = nums[i];
while(!s.empty() && s.top() <= minVal) s.pop();
if(!s.empty() && s.top() < curr) return true;
s.push(nums[i]);
}
return false;
}
};
main(){
vector<int> v = {-1,3,2,0};
Solution ob;
cout << (ob.find132pattern(v));
}입력
[-1,3,2,0]
출력
1
복잡도 분석
이 알고리즘은 각 원소가 스택에 최대 한 번 push되고 최대 한 번 pop되므로 시간 복잡도는 O(n)입니다. 또한 최솟값 배열과 스택을 위해 추가 공간이 필요하므로 공간 복잡도 역시 O(n)입니다. 완전 탐색 방식의 O(n²) 이상 접근법에 비해 훨씬 효율적인 해법입니다.