리트코드 - 334. Increasing Triplet Subsequence

https://leetcode.com/problems/increasing-triplet-subsequence/description/

Increasing Triplet Subsequence - LeetCode

 

정수 배열 nums가 주어졌을 때, i < j < k, nums[i] < nums[j] < nums[k]와 같은 인덱스의 삼중 배열(i, j, k)이 존재하면 참을 반환한다. 그러한 인덱스가 존재하지 않으면 false를 반환한다.

 

처음에 생각했던 풀이는 enumerate와 combination을 활용해서 (인덱스, 값)으로 이뤄진 조합을 구하고, 비교하는 방식을 생각했었는데, 그럴 경우 조합을 보관하기 위한 공간복잡도가 발생한다고 생각했다.

또한 그 조합들을 각각 비교하는 과정에서 시간복잡도가 O(n^2)이 발생한다고 생각했다.

 

그래서 다른 풀이를 참고했다.

 

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = second = float("inf") # O(1)

        for num in nums: # O(n)
            if num <= first: # O(1)
                first = num # O(1)
            elif num <= second: # O(1)
                second = num # O(1)
            else:
                return True
        return False

 

 

추가적인 배열을 생성하지 않고, 부분 배열의 첫번째 값과 두번째 값을 더해주는 변수 first, second를 생성해서 nums를 한번만 순회해서 비교할 수 있도록 하였다.

일단 삼중배열의 조건은 인덱스도 증가하고, 값도 증가하여야 하는 조건을 가진다. 따라서 다음과 같은 세가지 조건을 설정했다.

1. 첫번째 값보다 작을 경우에는 가장 작은 값이므로 첫번째 값에 할당한다.

2. 첫번째 값보다 크고 두번째 값보다 작을 경우에는 두번째 값에 할당한다.

3. 첫번쨰 값보다 크고 두번째 값보다 클 경우에는 삼중배열에 해당하므로 True를 반환한다.

 

배열을 모두 순회할 때까지 True가 반환되지 않으면, 삼중배열이 존재하지 않는다는 의미이므로 False를 반환한다.