문제 링크

내 코드

놓친 것들.

• 마지막 원소 생각 X
• integer 범위 생각 X

0ms, 89.44MB

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        long long sum{};
        for(int num : nums) sum += num;

        long long leftSum{};
        int answer{};
        for(int i{};i<nums.size() - 1;++i) {
            leftSum += nums[i];
            sum -= nums[i];
            if(leftSum >= sum) ++answer;
        }
        

        return answer;
    }
};

Solution

Approach 1: Prefix Sum Array

• 4ms, 97.13MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int n = nums.size();
        // Prefix sum array to store cumulative sums
        vector<long long> prefSum(n);
        prefSum[0] = nums[0];

        // Build prefix sum array
        for (int i = 1; i < n; i++) {
            prefSum[i] = prefSum[i - 1] + nums[i];
        }

        int count = 0;
        // Check each possible split position
        for (int i = 0; i < n - 1; i++) {
            // Sum of left part (0 to i)
            long long leftSum = prefSum[i];
            // Sum of right part (i+1 to n-1)
            long long rightSum = prefSum[n - 1] - prefSum[i];

            if (leftSum >= rightSum) {
                count++;
            }
        }

        return count;
    }
};

GPT

이 코드는 주어진 배열 nums를 두 부분으로 나누었을 때, 왼쪽 부분의 합이 오른쪽 부분의 합 이상인 경우의 개수를 계산하는 문제를 해결합니다.
핵심 아이디어는 prefix sum (누적 합) 을 사용하여 각 분할에서 빠르게 합을 계산하는 것입니다.

---

🔍 문제 분석

• nums 배열을 한 번만 분할할 수 있음 ([0..i]와 [i+1..n-1])
• sumLeft = nums[0] + ... + nums[i]
• sumRight = nums[i+1] + ... + nums[n-1]
• sumLeft ≥ sumRight를 만족하는 i의 개수를 반환

---

📌 코드 분석

1️⃣ 변수 초기화

int n = nums.size();
vector<long long> prefSum(n);
prefSum[0] = nums[0];

• n: 배열의 크기
• prefSum: 누적 합(prefix sum) 배열
  • prefSum[i] = nums[0] + nums[1] + ... + nums[i]

---

2️⃣ 누적 합 배열 생성 (Prefix Sum)

for (int i = 1; i < n; i++) {
    prefSum[i] = prefSum[i - 1] + nums[i];
}

• 누적 합을 사용하면 특정 구간의 합을 O(1)로 계산 가능
  • prefSum[i]는 nums[0]부터 nums[i]까지의 합을 저장
  • prefSum[n-1]은 nums 전체의 합

✅ O(n) 으로 미리 계산하여 이후 빠른 쿼리 수행 가능

---

3️⃣ 가능한 분할 위치 확인

int count = 0;
for (int i = 0; i < n - 1; i++) {
    long long leftSum = prefSum[i];
    long long rightSum = prefSum[n - 1] - prefSum[i];

    if (leftSum >= rightSum) {
        count++;
    }
}

• leftSum = prefSum[i] → nums[0]부터 nums[i]까지의 합
• rightSum = prefSum[n-1] - prefSum[i] → nums[i+1]부터 nums[n-1]까지의 합
• leftSum >= rightSum 이면 count++

✅ 각 i에 대해 O(1)`로 합을 계산할 수 있으므로 전체 연산은 O(n)

---

4️⃣ 결과 반환

return count;

✅ count에 저장된 가능한 분할 개수를 반환

---

📌 예제 실행

vector<int> nums = {10, 4, -8, 7};
Solution sol;
cout << sol.waysToSplitArray(nums);

Step 1: 누적 합(prefix sum) 생성

i	nums[i]	prefSum[i]
0	10	10
1	4	10 + 4 = 14
2	-8	14 + (-8) = 6
3	7	6 + 7 = 13

✅ prefixSum = [10, 14, 6, 13]

---

Step 2: 분할 검사

i	leftSum = prefSum[i]	rightSum = prefSum[n-1] - leftSum	비교 (leftSum ≥ rightSum?)
0	10	13 - 10 = 3	✅ (10 ≥ 3)
1	14	13 - 14 = -1	✅ (14 ≥ -1)
2	6	13 - 6 = 7	❌ (6 < 7)

✅ 가능한 i는 0과 1 → 결과 = 2

---

⏱ 시간 복잡도 분석

연산	시간 복잡도
누적 합 계산	$O(n)$
분할 개수 계산	$O(n)$
전체 시간 복잡도	$O(n)$

---

💡 최적화

• prefixSum 배열을 따로 만들지 않고 변수 하나만 사용하여 최적화 가능

개선된 코드 (공간 최적화)

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        long long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int count = 0;
        long long leftSum = 0;

        for (int i = 0; i < nums.size() - 1; i++) {
            leftSum += nums[i];
            long long rightSum = totalSum - leftSum;

            if (leftSum >= rightSum) {
                count++;
            }
        }

        return count;
    }
};

🚀 개선점

• totalSum을 먼저 계산하여 누적 합 배열 없이 바로 사용
• O(n) 시간, O(1) 공간으로 최적화!

---

✅ 결론

✔ O(n)으로 효율적인 해결 가능!
✔ 누적 합(prefix sum) 활용하여 빠르게 구간 합 계산
✔ 공간 최적화로 O(1) 추가 메모리 사용 가능 🚀

Approach 2: Optimized Prefix and Suffix Sums

• 3ms, 89.36MB
• Complexity
  • Let $n$ be the length of the input array nums.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        // Keep track of sum of elements on left and right sides
        long long leftSum = 0, rightSum = 0;

        // Initially all elements are on right side
        for (int num : nums) {
            rightSum += num;
        }

        int count = 0;
        // Try each possible split position
        for (int i = 0; i < nums.size() - 1; i++) {
            // Move current element from right to left side
            leftSum += nums[i];
            rightSum -= nums[i];

            // Check if this creates a valid split
            if (leftSum >= rightSum) {
                count++;
            }
        }

        return count;
    }
};

GPT

이 코드는 배열을 두 부분으로 나누었을 때, 왼쪽 부분의 합이 오른쪽 부분의 합 이상이 되는 경우의 개수를 찾는 문제를 해결합니다.

기존 prefix sum 배열을 사용한 방식에서 공간 최적화( $O(1)$ 추가 공간) 를 적용한 버전입니다. 🚀

---

🔍 핵심 아이디어

1. 총합(rightSum)을 먼저 계산 → 처음에는 모든 원소가 오른쪽 부분에 있음.
2. 왼쪽에서 오른쪽으로 이동하며 왼쪽 부분(leftSum)을 증가시키고 오른쪽 부분(rightSum)을 감소.
3. 각 분할 지점에서 leftSum ≥ rightSum인지 확인 → 만족하면 count++.

✅ $O(n)$ 시간, $O(1)$ 공간에 해결 가능!

---

📌 코드 분석

1️⃣ 변수 초기화

long long leftSum = 0, rightSum = 0;

• leftSum: 왼쪽 부분의 합 (처음에는 0)
• rightSum: 오른쪽 부분의 합 (처음에는 전체 합)

---

2️⃣ 전체 합 계산

for (int num : nums) {
    rightSum += num;
}

• rightSum을 배열 nums의 총합으로 초기화.

---

3️⃣ 가능한 분할 위치 검사

int count = 0;
for (int i = 0; i < nums.size() - 1; i++) {
    leftSum += nums[i];   // 현재 원소를 왼쪽 부분으로 이동
    rightSum -= nums[i];  // 오른쪽 부분에서 제거

    if (leftSum >= rightSum) {  // 왼쪽 합이 크거나 같다면 유효한 분할
        count++;
    }
}

• 각 i에서 nums[i]를 왼쪽 부분으로 이동 (leftSum 증가, rightSum 감소).
• leftSum >= rightSum이면 유효한 분할 → count++.

---

4️⃣ 최종 결과 반환

return count;

✅ count에 저장된 유효한 분할 개수 반환.

---

📌 예제 실행

vector<int> nums = {10, 4, -8, 7};
Solution sol;
cout << sol.waysToSplitArray(nums);

Step 1: 전체 합(rightSum) 계산

rightSum = 10 + 4 + (-8) + 7 = 13

---

Step 2: 가능한 분할 위치 검사

i	nums[i]	leftSum (누적)	rightSum (총합 - leftSum)	leftSum ≥ rightSum?	count
0	10	10	3	✅ (10 ≥ 3)	1
1	4	14	-1	✅ (14 ≥ -1)	2
2	-8	6	7	❌ (6 < 7)	2

✅ 최종 결과 count = 2

---

⏱ 시간 복잡도 분석

연산	시간 복잡도
rightSum 계산	$O(n)$
for 루프	$O(n)$
전체 시간 복잡도	$O(n)$

✅ $O(n)$으로 최적화됨!
✅ 추가 공간 $O(1)$ $\rightarrow$ 메모리 효율적!

---

💡 핵심 최적화 포인트

1. 누적 합 배열 없이 rightSum을 직접 조정하여 공간 최적화( $O(1)$ )
2. leftSum과 rightSum을 한 번씩만 업데이트하여 $O(n)$ 유지
3. 배열을 한 번만 순회하는 방식으로 최대한 빠르게 처리

---

✅ 결론

✔ $O(n)$ 시간, $O(1)$ 공간으로 최적화된 코드!
✔ 메모리를 줄이면서도 prefix sum 기법을 그대로 활용 🚀
✔ 배열을 한 번만 순회하여 빠르게 해결 가능 ✅