(C++, Rust) - LeetCode (easy) 222. Count Complete Tree Nodes

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

Fair Candy Swap - LeetCode

이분탐색 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. alice 가 가진 candy, bob이 가진 candy 총량을 선언해 저장합니다.2. 서로에게 필요한 사탕 개수의 차이를 변수 diff를 선언해 저장해줍니다. alice의 사탕 총량에서 빼줘야 음수인 경우 alice가 더 필요하다는 것을 알 수 있으며 반대의 경우 bob이 더 필요하다는 것을 알 수 있습니다.3. 이분탐색을 위한 bob sizes를 오름차순으로 정렬해줍니다.

📔 풀이과정

1. alice size에 대해 for loop를 수행합니다.

2. 찾아야 하는 key는 a - diff입니다. 

3. bob size에 대해 해당 key의 lower_bound를 찾은 후

4. a - 찾은 값이 diff와 같다면 정답을 반환해줍니다.

---

📕 Code

📔 C++

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
        int aliceTotal = 0, bobTotal = 0, diff;
        for(auto a : aliceSizes) aliceTotal += a;
        for(auto b : bobSizes) bobTotal += b;
        diff = aliceTotal - (aliceTotal + bobTotal) / 2;
        sort(bobSizes.begin(), bobSizes.end());
        for(auto a : aliceSizes) {
            int key = a - diff;
            auto idx = lower_bound(bobSizes.begin(), bobSizes.end(), key);
            if(idx == bobSizes.end()) continue;
            if(a - *idx == diff)
                return {a, *idx};
        }
        return {};
    }
};

📔 Rust

impl Solution {
    pub fn fair_candy_swap(alice_sizes: Vec<i32>, bob_sizes: Vec<i32>) -> Vec<i32> {
        let alice_sum: i32 = alice_sizes.iter().sum();
        let bob_sum: i32 = bob_sizes.iter().sum();
        let diff: i32 = alice_sum - (alice_sum + bob_sum) / 2;
        let mut bob_sorted = bob_sizes.clone();
        bob_sorted.sort();

        for &a in &alice_sizes {
            let key = a - diff;
            match bob_sorted.binary_search(&key){
                Ok(idx) => {
                    if a - bob_sorted[idx] == diff {
                        return vec![a, bob_sorted[idx]];
                    }
                }
                _ => {
                    continue;
                }
            }
        }
        vec![]
    }
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.