PermMissingElem / TapeEquilibrium

배열 원소들의 합을 이용한 문제 풀이

절대값의 비교와 연산의 효율에 관한 문제였는데

PermMissingElem를 풀고나서 점수가 낮았던 문제점이
똑같이 생겨 TapeEquilibrium에서도 점수가 낮게나왔다.

PermMissingElem에서는 A배열을 sort()하고,
1부터 시작하는 변수 i를 이용해서
변수와 해당 변수의 인덱스를 가진 A[i]와 값이 다르다면 그것을 반환하는 식으로 짰었다.

결과는 퍼포먼스, 오류도 몇개있었는데
정렬을 쓰는것 자체가 성능측면에서 구리기도 해서 점수가 낮았다.

다른분이 푼 방식을 보면 by kninami

class Solution {
    public int solution(int[] A) {
        long N = A.length +1;
        long totalSum = (N*(N+1))/2;
        
        for(int i=0; i<A.length; i++){
            totalSum -= A[i];
        }
        
        return (int)totalSum;
    }
}

A배열의 모든 원소가 빠지지않을 경우의 합을 계산하고
그 합에서 원소를 하나씩 빼면 마지막에 반환된 totalSum이 빠진 원소라는 알고리즘으로 완성시켰다.

for문의 인덱스를 이용하는것 까지는 맞았는데
합을 이용해서 진행하는건 생각 못해서 처음 생각난 sort를 이용했는데 이거 때문에 점수가 낮게 나온것 같다.

TapeEquilibrium에서는
P값에 해당하는 -빼기 나오기전의 front 부분과 -이후에 back부분을 새로운 B배열의 원소에 집어넣어 sort()하는 걸로 만들었는데 이것도 역시 퍼포먼스나 다른 점수들이 너무 낮게 나왔다 :(

앞의 예제에서 썼던 합을 이용해 풀이과정을 만들어 보려고 했는데
최솟값을 어떻게 해야 결정 지을지 생각을 못해서 다른분의 예제를 참고했다. by 아브

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        int front = 0;
        int back = 0;
        for(int i = 0 ; i < A.length ; i++){
            back += A[i];   
        }
        
        int minDiff = Integer.MAX_VALUE;
        int p = 1;
        for(int i = 1 ; i < A.length ; i++){
            front += A[i-1];
            back -= A[i-1];
            p = i;
            minDiff = Math.min(minDiff, Math.abs(front - back));
        }
        
        return minDiff;
        
    }
}

minDiff = Math.min(minDiff, Math.abs(front - back) 을 이용해서
for문에서 최솟값을 갱신시키는것과, A배열의 총합인 back 변수에서 p값에 따라 빠지게되는
뒷부분의 연산을 간단하고 효율적으로 처리하신것 같다.

back부분의 처리에 관해 다시 생각해보자면 for문을 돌면서 초기화가 아니라
계속 연산되면서 A[0]값이 빠지고 A[1], A[2] … 값이 계속 빠지는 과정을 어떻게 해야될지가
이번거에서는 제일 어려웠던것 같다.

PermMissingElem / TapeEquilibrium

JIHUN HONG