문제 개요
숫자 목록 nums가 주어졌을 때, 인덱스 순서가 i < j < k를 만족하면서 동시에 nums[i] < nums[k] < nums[j]가 성립하는 삼중항 (i, j, k)이 존재하는지 확인해야 합니다.
예를 들어 입력이 nums = [2, 12, 1, 4, 4]라면 결과는 참(True)입니다. 인덱스 (0, 1, 3)에 해당하는 값들 [2, 12, 4]가 2 < 4 < 12 조건을 충족하기 때문입니다.
풀이 전략
이 문제는 흔히 “132 패턴” 문제로 알려져 있으며, 세 겹의 반복문을 사용하는 순진한 방식은 O(n³)으로 매우 비효율적입니다. 대신 접두사 최솟값 배열과 스택을 함께 활용하면 선형 시간 O(n) 안에 해결할 수 있습니다.
- 최솟값 배열(left): 각 인덱스 i까지 등장한 값 중 최솟값을 미리 저장합니다. 이 값은 패턴에서 가장 작은 수(첫 번째 요소)가 될 수 있는 최적의 후보를 제공합니다.
- 단조 스택(st): 배열의 오른쪽 끝에서 왼쪽으로 이동하며 값을 쌓습니다. 현재 위치 왼쪽 구간의 최솟값 x보다 작거나 같은 요소는 후보에서 제외되므로, 스택에 남아 있는 값은 항상 x보다 큰 값뿐입니다.
알고리즘 단계
- n := nums의 크기로 설정합니다.
- 크기가 n인 배열 left를 정의하고, left[0] := nums[0]으로 초기화합니다.
- i를 1부터 n-1까지 증가시키며 left[i] := min(nums[i], left[i-1])을 계산합니다. (각 위치까지의 최솟값 누적)
- 정수형 스택 st를 하나 생성합니다.
- i를 n-1부터 1까지 감소시키며 다음을 반복합니다:
- x := left[i-1] (현재 위치 왼쪽 구간의 최솟값)
- st가 비어 있지 않고 st의 top이 x보다 작거나 같으면 계속 pop합니다.
- st가 비어 있지 않고, x < nums[i]이며 nums[i] > st.top()이면 true를 반환합니다. (조건을 만족하는 삼중항 발견)
- nums[i]를 st에 push합니다.
- 모든 반복이 끝날 때까지 찾지 못했다면 false를 반환합니다.
C++ 구현 예제
아래 구현을 통해 동작 과정을 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int>& nums) {
int n = nums.size();
vector<int> left(n);
left[0] = nums[0];
for (int i = 1; i < n; i++) {
left[i] = min(nums[i], left[i - 1]);
}
stack<int> st;
for (int i = n - 1; i >= 1; i--) {
int x = left[i - 1];
while (!st.empty() && st.top() <= x)
st.pop();
if (!st.empty() && x < nums[i] && nums[i] > st.top())
return true;
st.push(nums[i]);
}
return false;
}
};
bool solve(vector<int>& nums) {
return (new Solution())->solve(nums);
}
int main(){
vector<int> v = {2, 12, 1, 4, 4};
cout << solve(v);
}입력
{2, 12, 1, 4, 4}출력
1
핵심 정리
left 배열은 왼쪽 구간의 최솟값, 즉 패턴의 첫 번째 요소 후보를 담당하고, 스택은 오른쪽 구간에서 세 번째 요소 후보를 관리합니다. 현재 값 nums[i]가 이 두 후보 사이의 중간값 역할을 할 수 있는지만 검사하면 되므로, 불필요한 비교를 줄여 전체 배열을 한 번씩만 훑는 O(n) 연산으로 문제를 해결할 수 있습니다.