456. 132 Pattern

Medium

후기

square time으로 짜도 최적화만 잘 하면 통과가 되긴 합니다.

다만 O(N log N), 심지어는 선형 시간까지 노려볼 수 있는 문제입니다. 둘 다 정말 독창적이었습니다. 그 중에서 더 빠른 것에 집중하는 것이 좋으니, 선형 시간 풀이를 자세히 봅시다.

기반 아이디어도 인상적입니다.
사용한 알고리즘도 꽤나 유명한, 자주 등장하는 테크닉입니다. (다만 경험적으로, 이 테크닉이 현업에서 자주 등장하지는 않을 것 같습니다. 오로지 문제풀이 용도일 겁니다.)

잘 모르겠더라도 스포 당할 가치가 충분히 있습니다.

설명을 조금 자세히 적어뒀는데, 도움이 되셨으면 좋겠습니다.

풀이

핵심 아이디어부터 봅시다.

132 로 접근하는 건 꽤 까다롭습니다. 모든 유효한 구간을 저장하고, 그 구간들 중 어딘가에 속하는지 체크해봐야 하기 때문입니다. 물론 이진 탐색을 잘 써서 O(N log N)으로 줄여볼 시도는 할 수 있겠지만, 코드가 워낙 복잡해질 것 같네요.

그래서, 배열을 뒤집어봅시다. 231 문제가 됩니다. 그러면 접근법이 이렇게 바뀝니다.

지금까지 체크한 숫자들을 2 후보라고 합시다. 그 수보다 큰 수(3)가 들어왔다면 유효한 2가 됩니다.
새 숫자가 들어왔을 때, 그 숫자가 유효한 2중 하나보다 작으면 유효한 1이 됩니다. 따라서 231을 찾은 것으로 알고리즘이 종료됩니다.
어떤 시점에서 유효한 2가 여러개 있을 때, 그 중에서 가장 큰 것만 보면 됩니다. 나머지는 버려도 됩니다.

구간을 기록할 필요도 없어졌고, 모든 유효한 것들을 기록할 필요도 없어졌습니다. 문제가 더 간결해졌죠.

이제 이 접근법을 선형 시간으로 구현할 테크닉을 소개하겠습니다. 바로 모노토닉 스택입니다. 스택은 그냥 평범하게 내장 라이브러리에서 갖다 씁니다. 대신 저희가 코드를 잘 짜서 스택에 든 값들이 항상 모노토닉하도록 유지하는 테크닉입니다. 그래서 테크닉이라는 표현을 썼습니다.

이때 모노토닉은, 모든 원소가 항상 증가(a[i-1] ≤ a[i])하거나 항상 감소(a[i-1] ≥ a[i])하거나를 의미합니다. 당연히 둘 중 하나만 가능합니다.

대체로 패턴은 이렇습니다. 증가하는 스택 기준으로 봅시다. 수열을 순회하면서 스택에 값을 넣습니다. 만약 현재 원소가 스택 탑보다 크다면, 그냥 푸시하면 됩니다. 만약 현재 원소가 스택 탑보다 작다면, 푸시하면 모노토닉이 깨집니다. 그래서 현재 원소보다 작은 것들을 모조리 pop해서, 모노토닉이 되도록 수동으로 만듭니다. 그 다음 살포시 푸시하면 됩니다.

이 친구는 아주 사기적입니다. 사용할 수 있는 상황이라면, 무조건 O(N)의 시간복잡도를 보장하기 때문입니다. 그래서 문제가 N^2정도로 입력 배열을 탐색해야 할 것처럼 보이는데, 막상 N이 십만 이상이라면, 모노토닉 스택 응용 문제일 가능성을 한 번쯤 생각해봐야 합니다.

백준에서 관련 문제는 골드4~플레3까지 분포하고 있는 걸 봤습니다. 난이도 높은 스택 문제는 거의 다 이거라고 보시면 됩니다. 17298번 골드4 오큰수가 유명한 문제중 하나인데, 자잘한 조건이 없어서 이 테크닉 입문용으로 강추합니다. (구글링해가며 이해될 때까지 해보시길 추천드려요.) 특히 1725번 플레5 히스토그램 문제가 아주 유명한 유형입니다. 이것만 잘 익히면 플레 문제 몇 개를 날먹할 수 있습니다.

리트코드에는 모노토닉 스택 태그가 따로 있습니다.

본격적인 풀이입니다. 우선 상술한 것처럼 배열은 뒤집었습니다.

“유효한 2중 최댓값” 변수를 만들어둡시다. 일단은 그렇다고 가정해두고, 자세한 것은 후술하겠습니다. 배열을 순회하면서, 새 원소가 그 변수보다 작다면 유효한 1이므로 일고리즘을 즉각 종료시킵니다.

이 문제에서는 단조 감소(monotonic decreasing)를 쓸 겁니다. 새 원소가 스택 탑보다 작다면, 그냥 푸시합니다.

새 원소가 스택 탑보다 큰 경우를 봅시다. 그러면 스택 탑을 유효한 2로, 새 원소를 3으로 볼 수 있습니다. 그렇다면 이후에 유효한 2보다 작은 수가 발견된다면 그것이 유효한 1일 것이고, 알고리즘이 종료되겠죠.

이런 방식으로 스택 탑을 pop하고, pop한 숫자를 “유효한 2중 최댓값” 변수에 기록해둡시다. 본래 기존 최댓값보다 더 큰지를 판별하고자 max 함수 사용을 고려해야 하지만, 이 문제에서는 “유효한 2중 최댓값”보다 더 작은 수가 발견되면 즉각 알고리즘이 종료됩니다. 즉, pop된 숫자가 기존 최댓값보다 작은 경우는 애초에 스택에 들어가기도 전에 끝나므로 고려하지 않아도 됩니다. 또한 스택에 남아있는 숫자는 항상 현재 “유효한 2중 최댓값”보다 크다고 볼 수 있습니다.

모노토닉 스택의 특징은, 새 원소에 대해 pop해야 하는 숫자가 여럿일 수 있다는 것입니다. 그래서 while 반복문을 활용합니다. 새로운 스택 피크는 방금 pop한 것보다 더 크다는 점이 특징입니다. (문제 유형에 따라 “같거나 크게” 유지하기도, 단조 증가 스택을 쓰기도 합니다.)

마지막으로 새 원소 그 자체도 2 후보이므로 스택에 넣습니다.

이 내용을 갈무리한 것이 아래 코드입니다. 생각보다 간결합니다.

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.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

n == nums.length
1 <= n <= 2 * 10⁵
-10⁹ <= nums[i] <= 10⁹