2025. Maximum Number of Ways to Partition an Array - Streak 8

위 문제에서 정의된 동작을 함수 y=f(x)의 형태로 정의해보자.

g(y): 특정 위치 y를 기준으로 나눴을 떄
독립변수

• y: 바꿀 인덱스

종속변수

• 양쪽 값의 차이

f(x): 특정 자리 k로 바꾸는 함수
독립변수

• x: 바꿀 인덱스

종속변수

• ...?

상수

• k의 값
• 양쪽 범위

이 f를 정의하기가 어렵다.

---

f를 어떻게 정의해야 할까?
이 f의 독립변수의 개수가 현재 2개라, 시간복잡도가 n^2의 형태가 되고 있다.
따라서, f의 독립변수의 개수를 하나로 유지해두고 싶다.

 

pivot을 기준으로 좌측 - 우측을 수행하고, 이 값이 0인 것들의 갯수를 "조건을 만족하는 파티션"이라고 하자.

이렇게 정의해뒀을 때, 인덱스 i를 k로 바꿀때마다, 파티션 n-1개가 영향받는다.

i개의 파티션이 +diff만큼 변하고, n- i - 1개의 파티션이 -diff만큼 변함

 

즉, 바뀌는 k의 인덱스와, 영향을 받는 분할 포인트 pivot의 이동이 같이 진행된다.

즉, k와 자르는 인덱스 i를 하나의 루프로 합쳐 순회하면, 시간복잡도적 효율을 얻을 수 있다.

그러기 위해선 미리 각 인덱스가 갖는 값의 차이를 관리하는 맵이 존재해야 한다.
이 맵 두개를 각각 정의한 뒤, 맵의 갯수를 하나씩 이동해가면서 k의 변화 추적하면 O(n)만에 연산이 가능해진다.

왼쪽과 오른쪽의 적용되는 부호가 달라지기 때문에, 이렇게 관리해야 한다.

class Solution {
    public int waysToPartition(int[] nums, int k) {
        int n = nums.length;
        long[] psum = new long[n + 1];
        for(int i = 0; i<n; i++){
            psum[i+1] = psum[i] + nums[i];
        }

        // 좌측 끝부터 i까지, 즉 arr[i]가 늘어나면 파티션의 왼쪽이 늘어나는 위치
        Map<Long, Integer> leftSide = new HashMap<>();

        // 우측 끝부터 i까지, 즉 arr[i]가 늘어나면 파티션의 오른쪽이 늘어나는 위치
        Map<Long, Integer> rightSide = new HashMap<>();

        for(int i = 1; i<n; i++){
            leftSide.merge(psum[i] * 2 - psum[n], 1, Integer::sum);
        }

        int ret = leftSide.getOrDefault(0L, 0);

        for(int i = 0; i<n; i++){

            if (i != 0){
                leftSide.merge(psum[i] * 2 - psum[n], -1, Integer::sum);
                rightSide.merge(psum[i] * 2 - psum[n], 1, Integer::sum);
            }

            long diff = k - nums[i];
            int now = leftSide.getOrDefault(-diff, 0) + rightSide.getOrDefault(diff, 0);
            ret = Math.max(now, ret);
        }
        return ret;
    }

}