[LeetCode] 334. Increasing Triplet Subsequence

[LeetCode] 334. Increasing Triplet Subsequence

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

 

 

 

 

결과

 

문제 풀이

 

아이디어

• 증가하는 K(3)개의 수를 찾는 문제로 일반화
• K개의 값이 증가하는 패턴을 찾기
• 그리디 알고리즘으로 접근

K개를 먼저 준비해두고, 0번 인덱스부터 값을 교체해가며 연속하는 배열을 찾아냄

 

 

class Solution {
    func increasingTriplet(_ nums: [Int]) -> Bool {

// kLengthArray는 현재까지 발견한 k개의 증가하는 수열을 저장
        var k = 3
        var kLengthArray = Array(repeating: Int.max, count: k - 1)
        
        for num in nums {
            for i in 0..<(k - 1) {
                if num <= kLengthArray[i] {
                    kLengthArray[i] = num // 적절한 위치에 값을 넣음
                    break
                }
                // 마지막 값보다 더 크면 k개의 수가 완성됨
                if i == k - 2 {
                    return true
                }
            }
        }
        return false // k개의 증가하는 수열이 없는 경우
    }
}