[Codility(코딜리티)] Lesson3. TapeEquilibrium (100%)

Lesson 3 Time Complexity - TapeEquilibrium (Java Solution)

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

TapeEquilibrium coding task - Learn to Code - Codility

---

문제

N개의 정수들로 구성된 비어있지 않은 A 배열이 있다

어떠한 정수 P (0<P<N)가 있고,

P를 기준으로 A배열을 자른다 

그리고,

A[0], A[1], .. A[P-1]

A[P+1], A[P+2],... A[N]

두 값의 차를 구한다

그리고 가장 작은 절대값을 출력하자

 

예를들어,

A = {3,1,2,4,3}으로 주어졌다. 그러면 N=5이고, P는 0<P<5 사이의 값이다

P = 1 -> |3-10| = 7

P = 2 -> |4-9| = 5

P = 3 -> |6-7| = 1

P = 4 -> |10-3| = 7

즉, 1이 답이다 

 

해결

단순하게 문제 그대로 풀었다

A 배열의 총합을 구하고, 배열을 반으로 나눴을 때,

앞의 값들의 합을 저장할 변수(front)를 정의한다 

그리고 N-1만큼 반복하면서, 

front에 값을 저장하면서, 동시에 절대값을 구한다

그리고 저장된 절대값보다 작을 때만 값을 return 한다

public class TapeEquilibrium {

    public int solution(int[] A) {
        int N = A.length;

        int sum = Arrays.stream(A).sum();
        int front = 0;
        int result = 0;

        for (int i=0; i<N-1; i++) {
            front += A[i];
            int diffAbs = Math.abs(sum-2*front);
            if (i==0) {
                result = diffAbs;
            } else {
                result = diffAbs < result ? diffAbs : result;
            }
        }

        return result;
    }

자바 11에서는 100%인데, 

자바 8에선 94%가 나왔다

이전에도 같은 문제가 있었다

그때 stream을 사용해서 풀었는데, 성능이 좋지 않았던 생각이 났다

그래서 단순 for문을 반복해 sum을 구한 후, 풀었더니 자바 8에서도 100%가 나왔다

앞으로 stream을 사용할 땐, 자바 11로 풀어야겠다

public class TapeEquilibrium {

    public int solution(int[] A) {
        int N = A.length;
        
        int sum = 0;
        for (int i=0; i<A.length; i++) {
            sum += A[i];
        }
        
        int front = 0;
        int result = 0;

        for (int i=0; i<N-1; i++) {
            front += A[i];
            int diffAbs = Math.abs(sum-2*front);
            if (i==0) {
                result = diffAbs;
            } else {
                result = diffAbs <= result ? diffAbs : result;
            }
        }
        return result;
    }
}