LeetCode888. Fair Candy Swap

1. 문제(원본)

Alice and Bob have candy bars of different sizes: A[i] is the size of the i-th bar of candy that Alice has, and B[j] is the size of the j-th bar of candy that Bob has.

Since they are friends, they would like to exchange one candy bar 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 sizes of candy bars they have.)

Return an integer array ans where ans[0] is the size of the candy bar that Alice must exchange, and ans[1] is the size of the candy bar that Bob must exchange.

If there are multiple answers, you may return any one of them.  It is guaranteed an answer exists.

 

Example 1:

Input: A = [1,1], B = [2,2] Output: [1,2]

Example 2:

Input: A = [1,2], B = [2,3] Output: [1,2]

Example 3:

Input: A = [2], B = [1,3] Output: [2,3]

Example 4:

Input: A = [1,2,5], B = [2,4] Output: [5,4]

 

Note:

• 1 <= A.length <= 10000
• 1 <= B.length <= 10000
• 1 <= A[i] <= 100000
• 1 <= B[i] <= 100000
• It is guaranteed that Alice and Bob have different total amounts of candy.
• It is guaranteed there exists an answer.

2. 문제

두 개의 배열을 입력 받아 양쪽 배열의 인덱스의 합이 같아 지는 경우를 찾아 교환하라 

그리고 그 교환되어지는 수를 새로운 배열로 만들어 반환하라

3. 나의 답

class Solution {

 func fairCandySwap(_ A: [Int], _ B: [Int]) -> [Int] {

        var result = Array(repeating: 0, count: 2)

        let sumA = A.reduce(0) { $0 + $1 }

        let sumB = B.reduce(0) { $0 + $1 }

        let fair = (sumA + sumB) / 2

 

        for index in 0..<A.count {

            for target in 0..<B.count where (fair - sumA + A[index]) == B[target] {

                result[0] = A[index]

                result[1] = B[target]

                return result

            }

        }

        return result

    }

}

4. 다른 유저의 답

#1

class Solution {

    func fairCandySwap(_ A: [Int], _ B: [Int]) -> [Int] {

        let sumA = A.reduce(0, +)

        let sumB = B.reduce(0, +)

        let setB = Set<Int>(B)

        let target = (sumA + sumB) / 2

        let delta = target - sumA

        var rlt: [Int] = [0,0]

        for candy in A {

            let b = candy + delta

            if setB.contains(b) {

                rlt[0] = candy

                rlt[1] = b

                return rlt

            }

        }

        return rlt

    }

}

5. 마무리

이번 문제는 진짜 오랫동안 생각하고 고민을 많이 했다. 물론 처음에는 문제를 금방 풀어냈지만 처음에 풀어낸 방법은 문제에 충실하여 반복문을 무려 5번이나 사용했다. 거기에 4중 반복문이었기  때문에 양이 많아질수록 시간이 많이 걸릴 것이라는 생각이 들었고 새로운 방법과 규칙을 찾아내기 위해 노트에다가 여러가지의 가설을 세워서 만들어 보았다. 

덕분에 조금 더 빠르게 해결할 수 있는 방법을 찾아내었고 문제를 풀 수 있었다.

해결 후 다른 유저의 답을 보니 swift의 답은 하나뿐이었고 비슷하게 푼 것 같았지만 Set을 활용하여 중복을 우선 제거 후 풀었다는 것에 하나 더 배워갈 수 있는 문제가 되었던 것 같다.