[LeetCode] 334. Increasing Triplet Subsequence 해설 및 풀이 (Python)

LeetCode 334. 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

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

 

한글 해석

334. 증가하는 세 수의 부분 수열 (Increasing Triplet Subsequence)

정수 배열 nums가 주어질 때, 인덱스 (i, j, k)가 존재하여 i < j < k 이고 nums[i] < nums[j] < nums[k] 를 만족하는 경우가 있으면 true를, 그렇지 않으면 false를 반환하세요.

예시:

예시 1:

• 입력: nums = [1, 2, 3, 4, 5]
• 출력: true
• 설명: i < j < k를 만족하는 어떤 세 수를 선택하더라도 조건을 만족합니다.

예시 2:

• 입력: nums = [5, 4, 3, 2, 1]
• 출력: false
• 설명: 조건을 만족하는 세 수가 존재하지 않습니다.

예시 3:

• 입력: nums = [2, 1, 5, 0, 4, 6]
• 출력: true
• 설명: (3, 4, 5) 인덱스의 값들인 0 < 4 < 6이 조건을 만족합니다.

---

제약 사항:

• 배열의 길이: 1 <= nums.length <= 500,000
• 각 요소의 범위: -2^31 <= nums[i] <= 2^31 - 1

---

추가 과제 (Follow up):

• 시간 복잡도 O(n), 공간 복잡도 O(1)으로 해결할 수 있나요?

 

문제 유형

배열

그리디 알고리즘

 

풀이 방법 도출

 

이 문제의 핵심은 i < j < k 인덱스에 대해 nums[i] < nums[j] < nums[k]를 만족하는 "세 수의 오름차순"을 찾는 것입니다.

 

1. 배열을 순회하면서 현재까지 본 숫자 중 가장 작은 값(first)과 다음으로 작은 값(second)을 저장합니다.
2. 새로운 숫자가 first보다 작으면 first를 갱신합니다.
3. 새로운 숫자가 first보다는 크고 second보다는 작으면 second를 갱신합니다.
4. 새로운 숫자가 second보다 크면 오름차순 세 수가 존재하기 때문에 True를 반환합니다.
5. 탐색을 끝낸 뒤 조건에 만족하는 세 수를 찾지 못하였다면 False를 반환합니다.

 

시간 복잡도

• 시간 복잡도 : O(n) -> 배열을 한 번만 순회

---

핵심 코드 삽입 및 설명

from typing import List
 
 class Solution:
     def increasingTriplet(self, nums: List[int]) -> bool:
         # 첫 번째로 작은 값과 두 번째로 작은 값을 무한대로 초기화
         first = second = float('inf')
         
         for num in nums:
             if num <= first:
                 # num이 가장 작은 값이라면 first 갱신
                 first = num
             elif num <= second:
                 # num이 first보다는 크지만 second보다는 작으면 second 갱신
                 second = num
             else:
                 # num이 first와 second보다 모두 크면 조건 만족
                 return True
         
         # 세 수를 만족하는 조합이 없으면 False 반환
         return False