Codility -6 TapeEquilibrium(Java)

( https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ ) 

 

Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.

내 초기 풀이

 1) P를 기준으로 왼쪽합을 구하고 (첫 번째 for문)

 2) P를 기준으로 오른쪽합을 구하고 (두 번째 for문)

 3) 왼쪽합과 오른쪽합을 뺀 후, 절대값 처리를 해주고

 4) 왼쪽합 - 오른쪽합들을 계속 비교하여 min함수에 저장 후 반환

 

이런 식으로 풀었지만 점수는 15점.. 그리고 또 이중 for문을 사용하는 함정에 걸림.

 

class Solution {
    public int solution(int[] A) {
  
        int dif = 0;
        int min = 0;
        for (int i = 0; i < A.length - 1; i++){
            int pL = 0;
            int pR = 0;
            pL = pL + A[i];
            for (int j = i + 1; j < A.length; j++){
                pR = pR + A[j];
            }
            dif = pL - pR;
            if (dif < 0){
                dif = -dif;
            }
            if (i == 0){
                min = dif;
            }
            if (min > dif && i != 0){
                min = dif;
            }
        }
        return min;
    }
    
}

- 이 문제를 풀기 위해서는, 구간을 나눈 후 그 기준으로 각각 왼쪽 값, 오른쪽 값을 구해

- 두 값을 뺀 결과를 구한 후 절대값을 씌워

- 가장 차이가 적은 값을 리턴하는 것.

 

베스트 코드

package codility.practice;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TapeEquilibrium {
   
        
     public static void main(String[] args) {
            int[] A = {3, 1, 2, 4, 3};
            System.out.println("결과 : " + solution(A));
     }
     
     public static int solution(int[] A) {
         List sumList = new ArrayList();
         
         int left = 0;
         int right = 0;
         int sum = 0;
         
         for (int i : A) sum += i;
         
         for (int j = 1; j < A.length; j++) { 
             left += A[j - 1]; // 두 구간의 합 구하기
             right = sum - left;
             sumList.add(Math.abs(left - right)); // 결과값 저장
         }
         return (int)Collections.min(sumList); // 결과값 중 최소값 리턴
     }
    
}

이 문제의 포인트는 시간 복잡도를 0(n)으로 만들기 위해 각 조건을 효율적으로 생각해야 된다는 것.

 

* 주요 개념

 -  Math.abs

 - Collections.min

 - List와 ArrayList.

 

 

* 베스트 코드 참조

( https://cchoimin.tistory.com/entry/Codility-TapeEquilibrium-100%EC%A0%90 )