[codility] TapeEquilibrium

TapeEquilibrium

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

Task Score

100%

Correctness

100%

Performance

100%

---

 

먼저 보여줄 소스는 correctness 100%에 performance 0%인 코드.. 이것은 앞으로 많이 보게 될 내모습 ㅎㅎㅎ........ 그런데 원래 91%였는데 같은 소스를 넣었는데 왜 50퍼가 되었을까.. 코딜리티에서 시간복잡도 제한을 바꾼건가..

뭐 이러나저러나 50%를 받았고, 일단 설명을 해보겠다.

P값을 1부터 N-2까지 왔다갔다하면서 다 비교해봤다.

설명을 적고보니까 왜 performance가 0% 나왔는지 알 것 같기도 하고 ^^! ㅋㅋㅋㅋㅋㅋㅋ..하...

 

 
x
// you can also use imports, for example:
// import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int solution(int[] A) {
        int min = Integer.MAX_VALUE;
        
        for (int i = 1; i < A.length; i++) {
            
            int before = 0;
            int after = 0;
            
            for (int j = 0; j < i; j++) {
                before += A[j];
            }
            
            for (int j = i; j < A.length; j++) {
                after += A[j];
            }
            
            
            if (min > Math.abs(before - after))
                min = Math.abs(before - after);
        }
        
        return min;
    }
}

 

그래서 다시 풀어보았다.

for문을 이중으로 쓰지않고 할 수 있는 방법을 이렇게 저렇게 바꿔가면서 찾아봤는데, 갑자기 programmers의 별삼각형 문제가 생각났다. 다른 분의 풀이에서 for문을 두번 돌려서 하나하나 처리하지 않고 하나로 별 개수 증가시키는 작업과 결과를 증가시키는 작업을 한번에 처리했던 그 방법.. 위의 풀이처럼 굳이 내가 P값을 i로 정해서 반복해 줄 필요가 없는 거였다.

그래서 어떻게 하면 그런 식으로 한 번에 처리 할 수 있을까? 앞부분을 더해주는 작업과 뒷부분을 더해주는 작업을 내가 하나로 줄여버릴 수 없을까? 하고 고민했다. 답은 있었다. 그냥 총합에서 앞부분을 빼주면 뒷부분이 되는 거였다 ^^.. 와 이걸 왜 생각 못했지..

공간복잡도는 O(N)이므로 단일 for문 두 개 쓰는 것은 제한 내였다. 그래서 먼저 총합을 구해주고, 앞부분을 구한 뒤 뒷부분은 총합에서 앞부분의 값을 빼주는 식으로 구하고, min값 계산은 위에서 했던 방식과 같게 하되 if문을 빼버리고 Math클래스의 메소드를 사용했다.

 

 
xxxxxxxxxx
// you can also use imports, for example:
// import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int solution(int[] A) {
        int total = 0;
        int before = 0;
        int after = 0;
        int min = Integer.MAX_VALUE;
​
        for(int i = 0; i < A.length; i++)
            total += A[i];
​
        for(int i = 1; i < A.length; i++) {
            before += A[i - 1];
            after = total - before;
            min = Math.min(min, Math.abs(before - after));
        }
​
        return min;
    }
}