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

 문제

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까지입니다.

 풀이

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        if(A.length == 0) return 1;
    	
    	int res=0;
    	boolean [] copyA = new boolean[A.length+2];
    	
        for(int i=0; i<A.length; i++){
        	copyA[A[i]] = true;
        }
        
        for(int i=1; i<copyA.length; i++){
        	if(copyA[i] == false) res = i;
        }

        return res;
    }
}

이전글 방법1(2021/01/04 - [Codility/Lesson] - Lesson 3(Time Complexity) - PermMissingElem (방법1))과는 다르게

정렬을 사용하지 않고 배열을 하나 더 만들어서 각 숫자를 확인 후 변경되지 않은 값을 반환하는 형식으로 구현하였습니다.

 

 

 결과

코드 제출 화면1

 

코드 제출화면 2

제출 결과입니다.

복잡도가 N Or N*log(N)이 나왔습니다.

소스 코드를 보면 반복문 2번만 사용한거라 N으로 간주됩니다만 결과는 N Or N*log(N) 이 나왔네요.

테스트 결과 비교

 

배열을 이용한 방식

 

비교 결과

처리 속도가 빨라졌음을 확인 할 수 있습니다.