LeetCode: 888. Fair Candy Swap

https://leetcode.com/problems/fair-candy-swap/description/

Alice and Bob have a different total number of candies. You are given two integer arrays aliceSizes and bobSizes where aliceSizes[i] is the number of candies of the ith box of candy that Alice has and bobSizes[j] is the number of candies of the jth box of candy that Bob has.

Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy. The total amount of candy a person has is the sum of the number of candies in each box they have.

Return an integer array answer where answer[0] is the number of candies in the box that Alice must exchange, and answer[1] is the number of candies in the box that Bob must exchange. If there are multiple answers, you may return any one of them. It is guaranteed that at least one answer exists.

 

Example 1:

Input: aliceSizes = [1,1], bobSizes = [2,2]
Output: [1,2]
Example 2:

Input: aliceSizes = [1,2], bobSizes = [2,3]
Output: [1,2]
Example 3:

Input: aliceSizes = [2], bobSizes = [1,3]
Output: [2,3]
 

Constraints:

1 <= aliceSizes.length, bobSizes.length <= 104
1 <= aliceSizes[i], bobSizes[j] <= 105
Alice and Bob have a different total number of candies.
There will be at least one valid answer for the given input.

 

풀이

class Solution {
    func fairCandySwap(_ aliceSizes: [Int], _ bobSizes: [Int]) -> [Int] {        
        for i in 0 ..< aliceSizes.count {
            for j in 0 ..< bobSizes.count {
                var aliceSizes = aliceSizes
                var bobSizes = bobSizes
                let alice = aliceSizes[i]
                let bob = bobSizes[j]
                
                aliceSizes[i] = bob
                bobSizes[j] = alice
                
                if aliceSizes.reduce(0, +) == bobSizes.reduce(0, +) {
                    return [alice, bob]
                }
            }
        }
        return [aliceSizes[0], bobSizes[0]]
    }
}

정답인 것 같은데 시간 초과가 났다.

어떻게 고쳐야 할지 감이 안잡혀서 다른 사람들의 풀이를 보고 이해 하기로 함

class Solution {
    func fairCandySwap(_ aliceSizes: [Int], _ bobSizes: [Int]) -> [Int] {
        var set_b : Set<Int> = []
        var sum_a = 0
        var sum_b = 0
        var diff = 0
        
        for a in aliceSizes {
            sum_a += a
        }

        for b in bobSizes {
            set_b.insert(b)
            sum_b += b
        }
        
        diff = (sum_a - sum_b) / 2

        for a in aliceSizes {
            if set_b.contains(a - diff) {
                return [a, a - diff]
            }
        }

        return [0]
        
    }
}

수학적으로 풀었다.(수학으로 풀지 않은 코드는 없는 것 같다)

엘리스와 밥이 서로 하나씩 교환해서 총합이 같아지도록 하는 것이 목표이므로,

엘리스의 총합 'sum_a', 밥의 총합 'sum_b'

엘리스가 x를 주고 밥이 y를 받는 다면,

최종 앨리스의 총합 = sum_a - x + y

최종 밥의 총합 = sum_a - y + x

sum_a - sum_b = 2x - 2y

x - y = (sum_a - sum_b) / 2

즉, diff = (sum_a - sum_b) / 2

이렇게 수식이 완성 되고 diff는 엘리스와 밥이 서로 교환 후 값이 같아지는 조건이 된다.

따라서 엘리스가 주려는 사탕 x에 diff를 빼주면 어떤 사탕(x)을 줘야 하는지 알 수 있게 된다.

---

import Testing

struct PlaygroundTest {
    let solution = Solution()

    @Test func test1() async throws {
        #expect(solution.fairCandySwap([1,1], [2,2]) == [1,2])
    }
    
    @Test func test2() async throws {
        #expect(solution.fairCandySwap([1,2], [2,3]) == [1,2])
    }
    
    @Test func test3() async throws {
        #expect(solution.fairCandySwap([2], [1,3]) == [2,3])
    }
    
    @Test func test4() async throws {
        #expect(solution.fairCandySwap([1,1,2], [1,2,3]) == [1,2])
    }
}