codility Lesson 풀어보기 3

Codiliy Lesson 풀어보기 Day3.

 - 아직은 Easy 위주로 진행.

 

Codility Lesson 3. Time Complexity - TapeEquilibrium

public int solution(int[] A) {
    // write your code in Java SE 8
    int minNum = Integer.MAX_VALUE;
    int totalSum = 0, leftSum=0;

    for(int i : A)
        totalSum += i;

    for(int i=0; i<A.length-1; i++){
        leftSum += A[i];
        minNum = Math.min(minNum, Math.abs(leftSum - (totalSum-leftSum)));
    }

    return minNum;
}

 - for문 내에서 합계를 매번 구하도록 하면 타임아웃이 난다.

Detected time complexity :O(N)

 

https://app.codility.com/demo/results/trainingA9H573-HVU/

Test results - Codility

 

Codility Lesson 4. Counting Elements - FrogRiverOne

public int solution(int X, int[] A) {
    // write your code in Java SE 8
    int[] chkList = new int[X+1];
    for(int i=0, cnt=0; i<A.length; i++) {
        if(chkList[A[i]] != 1 && A[i]<= X){
            chkList[A[i]] = 1;
            cnt++;
        }
        if(cnt == X) return i;
    }
    return -1;
}

 - 모든 배열을 비교할 필요는 없고, X 까지 값 채워지는 순간까지만 비교하면 OK

 

https://app.codility.com/demo/results/trainingFU38QE-6B6/