정렬_LeetCode_minimize-maximum-pair-sum-in-array

https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/

Minimize Maximum Pair Sum in Array - LeetCode

접근 방법

1. 첫번째와 마지막 인덱스의 합 or 가운데 인덱스 둘의 합이 가장 클 것이다.

2. max로 정해진 인덱스를 제외하고, 이 외의 pair는 처음과 끝 index를 더해서 만든다.

-> 1. 의 가정이 틀림을 확인.

1. 처음과 마지막 index를 pop하면서, pair의 합을 비교한다.

 

실패 코드

시간 제한에 걸렸다.

class Solution {
    func minPairSum(_ nums: [Int]) -> Int {
        let arr = nums.sorted(by:<)
        // print(arr)
        var sol = Int.max

        var sumArray: Set<Int> = [] 
        
        for index in 0..<arr.count/2 {
            sumArray.insert(arr[index] + arr[arr.endIndex - 1 - index])
        }
        
         for minMax in sumArray {
             var tempArr = arr
             var anotherPair : [Int] = []
             var isRight: [Bool] = []
            
             if tempArr.count == 2 {
                 sol = minMax
             }


             for i in 0..<tempArr.count/2 {
                 anotherPair.append(tempArr.removeFirst() + tempArr.removeLast())
             }

             if anotherPair.max() == minMax && sol > minMax {
                 sol = minMax
             }
         }
        
        
        return sol
    }
}

 

정답 코드

생각해보니, sumArray의 element를 전부 비교할 필요가 없었다.

return sumArray.max()를 하기로한다.

Runtime: 2528 ms

Memory Usage: 18.6 MB

class Solution {
    func minPairSum(_ nums: [Int]) -> Int {
        let arr = nums.sorted(by:<)
        // print(arr)
        var sol = Int.max

        var sumArray: Set<Int> = [] 
        
        for index in 0..<arr.count/2 {
            sumArray.insert(arr[index] + arr[arr.endIndex - 1 - index])
        }
        
        return sumArray.max()!
    }
}

개선 코드

성능이 좋지 않음을 확인했다.

이를 개선해보고자 다른 이의 코드를 보고 swift로 변형해보았다.

Runtime: 2512 ms, faster than 87.50% of Swift online submissions forMinimize Maximum Pair Sum in Array.

Memory Usage: 18.2 MB, less than 81.25% of Swift online submissions for Minimize Maximum Pair Sum in Array.

class Solution {
    func minPairSum(_ nums: [Int]) -> Int {
        let arr = nums.sorted(by:<)
        // print(arr)
        var sol = 0

        for index in 0..<arr.count/2 {
            let partialSum = arr[index] + arr[arr.endIndex - 1 - index]
            sol = partialSum > sol ? partialSum : sol 
        }
        
        return sol
    }
}

크게 개선되지 않음을 볼 수 있다.

swift 언어적 특성이 아닐까...?