PrefixSum_Leetcode_2389. Longest Subsequence With Limited Sum [swift]

https://leetcode.com/problems/longest-subsequence-with-limited-sum/description/

 

문제접근

반환해야할 정답 array인 sol의 정의는 다음과 같다.

sol[i]는 아래의 조건을 만족해야한다.

• sol[i]는 nums 부분집합의 크기이다. 이 때, 부분집합의 크기가 최대여야 한다.
• nums의 부분집합은 합이 queries[i]보다 작거나 같아야 한다.

정답코드

해당 코드는 

13ms Beats5.56%로 성능이 매우 좋지 않다.

예상컨데, lastIndex를 찾는 반복문이 O(n^2)이기 때문이라 추측

 

시간 성능이 좋은 코드들을 찾아보니, lastIndex 구문을 binarySearch로 대체한 경우들이었다.

class Solution {
    func answerQueries(_ nums: [Int], _ queries: [Int]) -> [Int] {
        let n = nums.count
        let m = queries.count

        var sol = [Int](repeating:0, count: m)
        
        let sortedNums = nums.sorted()
        let prefixSum: [Int] = {
            var sums = [Int]()
            var sum = 0
            for value in sortedNums {
                sum += value
                sums.append(sum)
            }
            return sums
        }()

        for i in 0..<m {
            let query = queries[i]
            if let index = prefixSum.lastIndex(where: { $0 <= query }) {
                sol[i] = index + 1
            } else {
                sol[i] = 0
            }
        }
        
        return sol
        
    }
}