334. Increasing Triplet Subsequence

[문제]

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.

 

[TC]

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Constraints:

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

 

Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?

 

[접근]

실패 코드의 접근 방법은 두가지였다.

1. 조합

2. i 인덱스 기준으로 한 묶음 지어서 체크

 

[실패 코드 - 조합 ] C++ 

#include<algorithm>
#include<map>


class Solution {

public : bool m_bIsTriple;
public : int n;
public : int r;
public : vector<int> ret;
public : vector<int> clone;

public : map<int,int> m_map;

public:
    bool increasingTriplet(vector<int>& nums) {

        if(CheckMapPass(nums) == false)
            return false;

        n = nums.size();
        r = 3; // 3개만 뽑을 것
        clone = nums;
        m_bIsTriple = false;

        Combination(-1,ret);
    
        return m_bIsTriple;
    }

public:
     void Combination(int start, vector<int> b)
    {
        if(m_bIsTriple == true)
            return;

        if(r == b.size())
        {
            m_bIsTriple = CheckTriple(b);
        }

        for(int i = start +1; i < n; i++)
        {
            b.push_back(i);
            Combination(i,b);
            b.pop_back();
        }
    }

public:
     bool CheckTriple(vector<int> vCheck)
    {
        if((clone[vCheck[0]] < clone[vCheck[1]]) && 
            (clone[vCheck[1]] < clone[vCheck[2]]) && 
            (clone[vCheck[0]] < clone[vCheck[2]]))
            return true;

        return false;
    }

public:
    bool CheckMapPass(vector<int>& nums)
    {
        for(int i = 0 ; i < nums.size(); ++i)
        {
            if(m_map.find(nums[i]) != m_map.end())
                continue;
            m_map.insert(make_pair(nums[i],nums[i]));
        }

        if(m_map.size() < 3)
            return false;

        return true;
    }
};

[실패 코드 - 인덱스 그룹화] C# 

public class Solution
{
    public bool IncreasingTriplet(int[] nums)
    {
        if (nums.Length < 3) return false;

        for (int i = 1; i < nums.Length - 1; ++i)
        {
            if ((nums[i - 1] < nums[i]) && (nums[i] < nums[i + 1]))
                return true;
        }
        return false;
    }
}

[성공 코드] C#

public class Solution {
    public bool IncreasingTriplet(int[] nums) {
        if(nums.Length < 3) return false;

        int first = Int32.MaxValue;
        int second = Int32.MaxValue;

        for(int i= 0; i < nums.Length; ++i)
        {
            if(first >= nums[i])
                first = nums[i];
            else if (second >= nums[i])
                second = nums[i];
            else 
                return true;
        }
                
        return false;
    
    }
}

[성공 결과]

[시도]

[후기]

문제를 보자마자 떠올린 방법은 넘겨주는 순서에서 조합을 뽑은 후에 조합이 i < j < k ,성립된다면 true 로 정리할 예정이었다.

하지만, 조합 알고리즘은 TimeLimit 로 가로막혀서 다른방법을 찾다가, 잘못 찾은 방식이 인덱스 앞뒤로 하나씩 검사해서 성립하면 true 를 리턴하는것이었는데, 여기서부터 문제에 대한 이해도가 낮아졌다. 무조건 앞뒤만 체크해서 넘기는 것이 아니었는데, 도저히 이해가안가서 풀이를 봤는데 [1,2,0,3] 이런식에도 true 뜨도록 하는거보니까 완전 틀린 방식에서 하루이틀 해메고 있었다. 

 

결국 강의까지보고 이해를 하고나서야 생각이 틀린것을 인정하고, 답을 수정할 수 밖에 없었다.