Lesson 3(Time Complexity) - PermMissingElem (방법1)

 문제

An array A consisting of N different integers is given. The array contains integers in 
the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

정수형 배열(크기 N)이 주어지면 1부터 N+1 사이 값 중 누락된 값을 찾습니다.

배열값은 중복되지 않으며 입력값의 범위는 1부터 N+1까지입니다.

 

 풀이

// you can also use imports, for example:
import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        if(A.length == 0) return 1;
    	
        Arrays.sort(A);

        for(int i=0; i<A.length; i++){
            if( A[i] != i+1 ){
                return i+1;
            }
        }

        return A[A.length-1]+1;
    }
}

입력받은 배열을 오름차순으로 정렬합니다.
정렬 후 배열 인덱스와 값을 비교합니다.

 

예제로 나온 {2,3,1,5}의 배열의 경우 정렬되어 아래와 같이 저장됩니다.

인덱스	0	1	2	3
배열의 값	1	2	3	5

쉽게 연산하기 위해 인덱스에 1을 더해봅니다.

인덱스+1	1	2	3	4
값	1	2	3	5

인덱스+1의 값과 배열의 값이 다를 경우를 찾아 그 값을 반환합니다.

 

 

 결과

 

주소 : app.codility.com/demo/results/trainingJ24G2M-9JZ/

제출 결과1

제출결과2

제출 결과입니다.

정렬 로직이 들어가 있어서 복잡도가 N*log(N)이 나왔습니다.