[코테]코딜리티 - tapeEquilibrium

문제

문제 요약

• N개의 정수로 이루어진 배열 A가 매개변수로 주어진다.
• 0 < P < N 조건을 가진 정수 P가 주어지면 2개의 부분에 대한 연산을 수행하여 최소 값을 반환하라.
• 첫번째 구간은 A[0] + A[1] +...+A[P-1]
• 두번째 구간은 A[P+1] +...+A[N-1]
• 첫번째 구간 - 두번째 구간 = 값
• 위의 식에 의한 값을 P의 값 변화에 따라 비교하여 최소값을 반환한다.
• 2 <= N <= 100,000
• -1,000 <= 각 요소 <= 1,000

문제 분석

다음 단계에 따라 문제를 분석했다.

• 2개의 부분을 뺄셈하여 최소 값을 구해야한다.
• 부분의 뺄셈을 위하여 합 배열을 생성하고, P의 위치에 따라 총 합에서 계산을 해준다.
• 기존에 계산된 값과 비교하여 더 작은 값을 최종 반환 값에 대입한다.
• 시간복잡도는 N이 100,000이고, P는 N-1까지의 범위를 가지기 때문에 O(n^2)라고 할 수 있다. 즉 10억 번의 연산이 수행된다.
• 때문에 다양한 방법 중 구간별 합을 미리 저장하는 합 배열을 사용하여, 인덱스를 통한 합을 구하는 것에 시간복잡도를 단축하기로 하였다.
• 이렇게하면 최소값 비교까지 시간복잡도는 O(n)에 가깝다.

슈도코드

합 배열을 선언한다

for(A의 길이만큼){
	합 배열[index] = 합 배열[index-1] + A[index-1]
}

int형의 최대값을 비교할 변수에 저장한다.

for(A의 길이만큼){
	비교값 = Math.min(비교값, Math.abs(합배열 구간 연산값))
}

결과를 반환한다.

구현코드

class Solution{
	public int solution(int[] A){
    	int[] preSum = new int[A + 1];
        int answer = Integer.MAX_VALUE;
        
        for(int i = 1; i <= A.length; i++){
        	preSum[i] = preSum[i-1] + A[i-1];
        }
        
        for(int p = 1; p < A.length; p++){
        	answer = Math.min(answer, Math.abs(preSum[p] - (preSum[preSum.length-1] - preSum[p])));
        }
        
        return answer;
    }
}