[LeetCode] Increasing Triplet Subsequence

https://leetcode.com/problems/increasing-triplet-subsequence/description/?envType=study-plan-v2&envId=leetcode-75

 

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.

 

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

 

너무 어렵게 생각해서 풀었구나 싶은 문제...

랜덤하게 숫자가 들어간 int[]가 있고, 그 안에서 작은 순으로 나열된 3개 이상의 엘리먼트가 있으면 true를 리턴해야 한다.

이 때 그 3개 이상의 엘리먼트 사이에 다른 숫자가 있어도 상관 없다.

 

 

문제 풀이

재귀함수를 한 번 써보고 싶었는데, 자꾸 요청시간이 초과되어 실패하는 이슈가 발생했다^_ㅠ

찾아야 하는 나보다 큰 숫자의 수를 주는 식으로 찾으면 바로 리턴하도록 했는데...

결국은 성공하긴 했지만 뭔가 어영부영 겨우 해낸 느낌...

function increasingTriplet(nums) {
  let result = false;
  const filtered = [...new Set(nums)];
  if (filtered.length < 3) {
    return false;
  }
  // 숫자가 작은 순으로 나열된 3개 이상의 elements가 있으면 true(사이에 다른 수가 있어도 됨)
  const findBiggerThanMe = (index, count) => {
    if (count === 0) {
      result = true;
      return;
    }
    const isNeed = filtered.filter((f) => f > nums[index]);
    if (isNeed.length === 0) {
      return;
    }
    for (let i = index + 1; i < nums.length; i++) {
      if (!result && nums[i] > nums[index]) {
        findBiggerThanMe(i, count - 1);
      }
    }
  };

  for (let i = 0; i < nums.length; i++) {
    if (result) {
      break;
    }
    findBiggerThanMe(i, 2);
  }

  return result;
}

 

 

다른 풀이

다른 풀이를 참고해 보니 대부분 아래와 같은 로직으로 풀었더라.

단순하게 그냥.. 숫자 정렬 구현하듯이 풀면 그냥 빠르게 해결할 수 있었던 부분이었다...

var increasingTriplet = function (nums) {
  let first = Infinity; // smallest number so far
  let second = Infinity; // second smallest number so far

  for (let i = 0; i < nums.length; i++) {
    console.log(first, second, nums[i]);
    if (nums[i] <= first) {
      first = nums[i]; // update the smallest number
    } else if (nums[i] <= second) {
      second = nums[i]; // update the second smallest number
    } else {
      // we found a number larger than both first and second
      return true;
    }
  }

  return false;
};