Leetcode 334. Increasing Triplet Subsequence

 

링크는 

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

 

 

 

 

# 문제 이해

숫자 자료형의 배열이 주어졌을 때, 연속으로 증가하는 3개의 숫자가 있으면 True, 없으면 False 를 반환하는 작업

완전 탐색 문제가 아닌가 싶다.

 

 

 

 

# 방법

1. 다음 숫자가 크면 cnt += 1, 아니면 0

2. cnt 가 3이되면 return true, 아니면 계속 진행

3. 마지막까지 갔을때 cnt 가 3이하면, return false을 반환한다.

 

 

 

 

# Try 1. 완전탐색 - 실패

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        cnt = 1
        tmp = nums[0]
        for num in nums[1:]:
            if tmp < num: # num 이 크면 += 1
                cnt += 1
            else:
                cnt = 1
            tmp = num
            if cnt >= 3:
                return True
        return False

왜 안돼지? 나란히 있는 3개의 원소 아닌가? 그냥 증가하는 일련의 3개의 원소로 생각해서 풀어봐야할 것 같다.

 

 

 

 

# Try 2. DP - 실패

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        arr = [0]* len(nums)
        for idx in range(len(nums)):
            if idx == 0:
                arr[idx] = 1
            else:
                if nums[idx-1] < nums[idx]: # 지금 값이 이전값보다 크면
                    tmp =
                    arr[idx] = arr[idx-1] + 1 # 1 증가
                else:
                    arr[idx] = arr[idx-1] # 그대로
        return arr[-1] >= 3

부분증가 하는 함수로 DP를 사용해 풀이를 생각했지만 [6, 7, 1, 2]같은 부분은 보장해주지 않는 것 같다. 

 

 

 

 

# Try 3. Greedy - 성공

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n1, n2 = float('inf'), float('inf')
        for n in nums:
            if n <= n1:
                n1 = n
            elif n <= n2:
                n2 = n
            else:
                return True
        return False

 

그리디 알고리즘을 사용했다. 배열을 순회하면서 첫 번째 작은 값과 두 번째 작은 값을 추적하고, 추적을 통과하면, 세 번째 증가 값에 해당하여 증가하는 삼중항이 존재함으로 True를 반환했다.