[CodingBat/java] canBalance

구분

• Array - 3 

문제

https://codingbat.com/prob/p158767

CodingBat Java Array-3 canBalance

주어진 int배열을 두 부분으로 나누었을 때, 

각각 배열의 합이 같아질 수 있으면 true / 불가능 하면 false

 

풀이

경계를 포인터로 두고 합을 계산해나가기, 

항상 각 배열의 합을 구해줄 필요 없어서 효과적 

끝까지 탐색했지만 중간에 반환되지 않은경우,

같아지는 부분이 절대 존재하지 않으므로 false를 return 

 

 

주의

음수가 나올 수도 있으므로, 현재까지 더해진 각각 배열의 합의 크기를 비교하여 포인터를 옮기는 것으로는 답을 구해낼 수 없다.

 

코드

    public boolean canBalance(int[] nums) {

        //배열크기가 1 이하면 무조건 불가능
        if(nums.length<=1) return false;

        //인덱스포인터
        int mid = 1;

        // 왼쪽 배열의 합 (첫원소)
        int sumL = nums[mid-1];

        //오른쪽 배열의 합 (인덱스 1 ~ 끝까지)
        int sumR = 0;
        for(int i=mid; i<nums.length; i++){
            sumR+=nums[i];
        }

        while(mid<nums.length){
            if(sumR == sumL) return true; //합이 같으면 true
            sumL+=nums[mid];//왼쪽 배열을 한개 늘리기
            sumR-=nums[mid];//오른쪽 배열을 하나 줄이기
            mid++;
        }

        return false;//한바퀴 돌았는데도 못찾았으면 불가능한 경우

    }