Array Partition - LeetCode

문제 풀이 아이디어

문제가 일견 복잡하게 보이는 부분도 있지만 찬찬히 읽어보면 상당히 간단한 문제이다.

주어진 배열의 길이는 무조건 짝수로 따라서 앞에서 부터 인접한 숫자끼리 짝으로 묶을 수 있다. 각각의 묶음에서 최소값를 뽑아서 더한 합 중에서 최대 값을 구하면 된다.

그렇게 하기 위해서는 각각 짝의 최소값를 최대한 크게 만들어야 한다. 그렇게 하기 위해서는 작은 수는 작은 수끼리 묶어야하고 큰 수는 큰 수끼리 묶어야 한다. 작은 수와 큰 수를 묶게 되면 최소값은 작은 수가 되기 때문에 합계를 할 때 손해를 보기 때문이다.

작은 수와 큰 수를 각각 끼리끼리 묶는 가장 쉬운 방법은 주어진 배열을 정렬하고 앞에서 부터 인접한 숫자끼리 묶는 것이다. 문제에서 주어진 두 번째 예시 [6,2,6,5,1,2]를 보면 [1, 2, 2, 5, 6, 6]으로 정렬한 다음에 (1, 2), (2, 5), (6, 6)으로 묶었을 때 구하는 합이 최대가 된다.

다시 말하면 이는 오름차순으로 정렬한 다음에 홀수번째 숫자 (인덱스 기준으로 짝수)만 더하면 되는 것이다.

아마 문제에서 설명한 내용을 그대로 코드로 옮기려고 했다면 이런 직관적인 풀이를 발견하기 어려웠을 것이다. 앞으로도 문제를 풀 때 바로 코드를 쓰는데 집중하지 말고 한 번 더 생각하는 시간을 가지도록 해야겠다.

코드

class Solution {
    func arrayPairSum(_ nums: [Int]) -> Int {
        // 정렬하고
        let nums = nums.sorted()
        var ans = 0
        // 짝수 index만 더한다.
        for i in 0..<(nums.count / 2) {
            ans += nums[i * 2]
        }
        return ans
    }
}

숏코딩

고차함수를 활용하면 아래처럼 더 짧게 코드를 쓸 수도 있다.

class Solution {
    func arrayPairSum(_ nums: [Int]) -> Int {
        nums.sorted().enumerated().filter { $0.offset % 2 == 0 }.reduce(0) { $0 + $1.element }
    }
}