[C++] LeetCode : Increasing Triplet Subsequence

Question

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums [i] < nums [j] < nums [k]. If no such indices exists, return false.

 

정수 배열 nums가 주어질 때, 인덱스 i, j, k에 대하여, i < j < k를 만족하고, nums [i] < nums [j] < nums [k]를 만족하는 triplet이 있으면 true를 반환하라. 그렇지 않으면 false를 반환하라.

 

제약사항

• 배열 nums의 길이는  1 이상5 * 10^5 이하이다.
• -2^ 31 <= nums [i] <= 2^ 31 - 1

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

  모든 배열의 원소를 살펴보아야 하므로 배열의 길이를 n이라 하였을 때 BCR은 O(n)이다.

 

고려사항

---

 

Solution1 (Bruth Force)

3중 loop로 조건을 만족하는 세 원소를 찾는 방법이다. 시간 복잡도는 O(n^3)이다.

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        for(int i=0; i<n-2;i++){
            for(int j=i+1; j<n-1;j++){
                if(nums[i] >= nums[j]) continue;
                for(int k=j+1; k<n; k++){
                    if(nums[j] < nums[k]) return true;
                }
            }
        }
        return false;
    }
};

---

Solution2 

문제에서 시간 복잡도 O(n)과 별도의 공간을 사용하지 않고 풀어볼 것을 권장하고 있다. 즉, 각 원소를 한 번씩만 살펴보고 조건을 만족하는 경우가 있는지 찾아야 한다.

 

아이디어는 다음과 같다.

• 첫 번째 원소를 고정하고 세번째 원소를 찾는다고 할 때 찾는데 유리하려면, 두 번째 원소는 최대한 작아야 한다. 
• 하지만, 무조건 작은 값을 찾는다고 그게 정답이 되진 않는다. [4,3,5,2,6] 같은 경우 2를 가장 작은 값으로 찾아 2와 6을 첫 번째 원소로 하지만 조건을 만족한다고 판단하진 않는다. 따라서 특정 조건을 만족하게 값을 찾아야 한다. 

먼저, 첫 번째 원소를 배열의 0번째 index라고 가정하고, 두 번째 원소를 최대한 큰 값을 할당한다. 그리고 두 번째 index부터 third로 적절한 값을 판단하는 과정을 거친다. 

1. third값이 first값보다 작을 때, fisrt값을 third값으로 경신해준다
2. third값이 second값보다 크면 조건을 만족하는 경우로 true를 반환해준다.
3. thrid값이 first보다 클 때, second값을 third값으로 경신해준다.

 

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = nums[0], second = INT_MAX, third;
        
        for(int i=1; i<nums.size(); i++){
            third = nums[i];
            
            if(third < first){
                first = third;
            }else if(third > second){
                return true;
            }else if(third > first){
                second = third;
            }
        }
    
        return false;
    }
};

• Time complexity : O(n), 배열의 크기만큼만 탐색하면 된다.
• Space Complexity : O(1) 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/781/

Explore - LeetCode