(C++, Rust) - LeetCode (easy) 1013. Partition Array Into Three Parts With Equal Sum

https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/

LeetCode - The World's Leading Online Programming Learning Platform

간단 구현 문제였습니다.

📕 풀이방법

📔 풀이과정

1. 3등분으로 나눠지며 각 부분들은 전체 원소 합 / 3이 되어야 함을 생각하면 편합니다. 또한 부분들이 3등분을 초과하더라도 해당 부분을 합친다는 생각으로 구현해줍니다.

2. 모든 원소의 합을 변수 sum에 저장하고 arr의 원소를 순회하며 누적합을 더해주면서 sum / 3일 때의 index를 vector pivIdx에 저장합니다.

📔 정답 출력 | 반환

pivIdx가 3이상인지 여부를 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int sum = 0;
        int pivSum = 0;
        for(auto a : arr) sum += a;
        if(sum % 3) return false;
        pivSum = sum / 3;
        sum = 0;
        vector <int> pivIdx;
        for(int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            if(sum == pivSum) {
                pivIdx.push_back(i);
                sum = 0;
            }
        }
        return pivIdx.size() >= 3;
    }
};

📔 Rust

use std::convert::TryInto;
impl Solution {
    pub fn can_three_parts_equal_sum(arr: Vec<i32>) -> bool {
        let mut sum: i32 = arr.iter().sum();
        if sum % 3 != 0 {
            return false;
        }
        let piv_sum = sum / 3;
        sum = 0;
        let mut piv_idx:Vec<i32> = Vec::new();
        for (i, &num) in arr.iter().enumerate() {
            sum += num;
            if sum == piv_sum {
                piv_idx.push(i.try_into().unwrap());
                sum = 0;
            }
        }
        piv_idx.len() >= 3
    }
}

📕 Test Case

몇 가지 test case입니다

input

[1,-1,1,-1]

답

false

input

[1,-1,1,-1,1,-1]

답

true

---

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