[Codility] TapeEquilibrium

문제: app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

TapeEquilibrium coding task - Learn to Code - Codility

 

처음에 죄다 타임아웃 에러가 나서 50점도 안나와서 깜짝 놀랐는데 깜빡하고 System.out.println()을 안 지워준거였다...

어쩐지 시간 복잡도가 O(N^2)가 나올리가 없는데 ㅋㅋ ㅠㅠㅠ

 

정답률 92 코드

class Solution {
    public int solution(int[] A) {
        int sum = 0;
        int sumOfAll = 0;
        int lengthOfA = A.length;
        int min = 1001;
        int cal = 0;

        for(int a:A) {
            sumOfAll += a;
        }
        for(int i=0;i<lengthOfA-1;i++) {
            sum += A[i];
            sumOfAll -= A[i];

            cal = Math.abs(sum-sumOfAll);
            min = min>cal?cal:min;
        }
        return min;
    }
}

요소가 2개인 경우에 틀렸다.

lengthOfA-1 미만인 경우에만 for문을 돌다보니...

 

2개인 경우를 추가했다!

아니면 for문의 범위를 바꾸는 방법도 있다.

1부터 시작하고 A[i]가 아니라 A[i-1]에 대해서 계산한다던가의 식으로!

 

class Solution {
    public int solution(int[] A) {
        int sum = 0;
        int sumOfAll = 0;
        int lengthOfA = A.length;
        int min = 1001;
        int cal = 0;

        if(lengthOfA==2) {
            return Math.abs(A[0]-A[1]);
        }
        for(int a:A) {
            sumOfAll += a;
        }
        for(int i=0;i<lengthOfA-1;i++) {
            sum += A[i];
            sumOfAll -= A[i];

            cal = Math.abs(sum-sumOfAll);
            min = min>cal?cal:min;
        }
        return min;
    }
}