[Algorithm] Sherlock and Array

[Algorithm] Sherlock and Array

---

[Problem]

길이가 N인 배열 A가 있다. 

특정 위치 i의 원소에 대해서 좌/우의 부분 합이 같은 i를 찾아라. 

ex) A[0] + A[1] + . . . + A[i-1] = A[i+1] + A[i+2] + .... + A[n] 을 만족시키는 i

[Solve]

1) 

i를 기준으로 좌/우의 합이 같아야 한다.

초기 입력을 받을 시 입력 배열의 총 합을 같이 계산하여 중복 계산을 방지하였다. 

i를 기준으로 탐색 시, 탐색 대상을 줄이고자 i의 위치에 따라 좌/우 중에서 원소가 더 적은 쪽의 합을 계산하였다. 

부분합을 계산 후 초기 입력 시에 계산 한 전체의 합의 1/2이 되는지를 체크한다.

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

    public static int[] arr = null;

    

    public static void main(String[] args) {

        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

        

        

        Scanner s = new Scanner(System.in);

        

        int T = s.nextInt();

        

        for(int t=0; t<T; t++){

            int N = s.nextInt();

            int sum = 0;

            arr = new int[N];

            

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

                arr[n] = s.nextInt();

                sum += arr[n];

            }

            search(sum, N);

        }

        

    }// end method

    

    public static void search(int sum, int N){

    

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

            int tmpSum =0;

            

            if(i>N/2){

                for(int idx=i+1;idx<N;idx++)

                    tmpSum += arr[idx];

            }

            else{

                for(int idx=0; idx<i;idx++)

                    tmpSum += arr[idx];

            }

            

            if(tmpSum == (sum - arr[i])/2){

                System.out.println("YES");

                return ; 

            }

        }

        

        System.out.println("NO");

    }

}

=>>>>>>>> 하지만 몇 개의 Test case에 대해서 timeout이 발생하였다.

2) Timeout 해결 

i를 1부터 찾아가게 되므로, 

0 ~ i-1까지의 부분 합을 매번 계산하지 않고, 누적하여 계산할 수 있다. 

o(n^2)를 o(n)으로 줄일 수 있다. 

   public static void search2(int sum, int N){

        int tmpSum = 0;

        

        for(int i=1;i<=N-1;i++){

            tmpSum += arr[i-1];

            

            if(tmpSum == ((sum-arr[i])/2)){

                System.out.println("YES");

                return;

            }

        }

        System.out.println("NO");

    }