[JAVA] Codility Lesson 3(3) - Time Complexity : TapeEquilibrium

app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

 

Tasks

---

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어진다.
0 < P < N과 같은 정수 P는 이 테이프를 비어 있지 않은 두 부분으로 분할한다
: A[0], A[1], ..., A[P-1] 및 A[P], A[P + 1], ..., A[N-1].
두 부분의 차이는 다음 값이다
: |(A[0] + A[1] + ... + A[P - 1]) - (A[P] + A[P + 1] + ... + A[N - 1])|
N개의 정수로 이루어진 비어 있지 않은 배열 A가 주어지면 달성할 수 있는 최소 차이를 반환한다.
ex) 
--------------------------------------
int[] A = {3, 1, 2, 4, 3}
P = 1, 차이 = |3 - 10| = 7
P = 2, 차이 = | 4 - 9| = 5
P = 3, 차이 = | 6 - 7| = 1
P = 4, 차이 = | 10 - 3| = 7
최종 결과, 1 반환
--------------------------------------

 

 

Solution

---

import java.util.Arrays;

public static int solution(int[] A) {
    int[] B = new int[A.length-1];
    
    int L = 0;
    int R = 0;
    
    // 총합 구하기
    for ( int i : A )
    	R += i;
    
    // 왼쪽, 오른쪽 부분합 배열 B 저장
    for ( int i = 0; i < B.length; i++) {
    	L += A[i];
        R -= A[i];
        
        B[i] = Math.abs(L-R);
    }
    
    // 정렬
    Arrays.parallelSort(B);
    
    return B[0];
}

 

 

+...

---

Math.abs()

abs 메서드는 절대값을 반환한다.

음수를 양수로 변경, 양수는 그대로 표시하여 반환

단, int 또는 long의 경우 최소 음수인 경우에는 절대값이 아닌 음수를 그대로 리턴한다.

int a = -2147483648;                 // int 최소 음수
int b = -9223372036854775808;        // long 최소 음수
System.out.println(Math.abs(a));
System.out.println(Math.abs(b));

// -2147483648
// -9223372036854775808

 

Arrays.parallelSort() VS Arrays.sort()

java8 버전에서 parallelSort 메서드가 추가되었다.

parallelSort 메서드는 필요에 따라 여러 개의 스레드로 나뉘어 작업이 수행되어 정렬되는 속도가 빠르다.

sort 메서드는 항당 단일 스레드로 수행된다.

parallelSort를 사용하는 것이 항상 옳다고 생각할 수 있으나 멀티 스레드를 사용한다는 것은 그만큼 CPU를 더 많이 사용한다는 뜻이며, 실제로 parallelSort 메서드와 sort 메서드를 비교해보면 약 5000개 이후부터 parallelSort 메서드가 빠르다고 한다.

적은 데이터 처리에는 sort()

대량의 데이터 처리에는 parallelSort()