LeetCode (C/C++) 456. 132 Pattern

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

---

답지 풀이

nums[k]를 저장할 변수 mid를 INT_MIN으로 초기화 해준다.

반복문을 역순으로 탐색하며 현재 스택에 담긴 값이 있고, 해당 값이 현재 값보다 작다면 기존의 값을 모두 빼준다.

이 때 third에 pop()한 값을 저장하여, mid에 nums[k]를 저장한다.

 

이 과정까지 거치면 mid에는 nums[k], stack의 top()에는 nums[j] 값이 저장된다.

이 때 새로 들어오는 값이 third보다 작다면 nums[i] < nums[k] < nums[j] 가 성립되므로 true를 반환.

 

Topics를 보고 stack을 사용해야 한다는 건 알았지만, 활용할 수 없었다...

---

코드

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int size = nums.size();

        // nums[k]
        int mid = INT_MIN;

        stack<int> s;
        for (int i = size - 1; i >= 0; i--) {
            if (nums[i] < mid)
                return true;

            // s.top() = nums[j]
            while (!s.empty() && s.top() < nums[i]) {
                third = s.top();
                s.pop();
            }  
            s.push(nums[i]);
        }
        
        return false;
    }
};