코딜리티 레슨3 Time Complexity 2 - PermMissingElem

문제

 

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)].

Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

​

→ 문제는.. 배열 안에 비어있는 값을 찾으라는 것, ex) array = 1,2,3,5 는 4를 return

 

답변

 

1. 기존 배열을 순차적으로 정리하면 규칙이 쉽게 보인다.

2. 배열의 요소들은 1부터 배열길이+1 까지 존재한다.

3. 요소를 순차적으로 정리하면 [1, 2 ... N+1] 이 된다.

4. 요소에서 -1 을 하면 요소의 인덱스가 반환된다.

5. int 배열은 값이 없으면 0 으로 초기화

(String 이 null 인 것 처럼)

6. 0이 나오는 곳이 빈 곳이겠지? 코딩으로 작성

​

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int val = 0;
        int[] newArr = new int[A.length+1];
        
        for(int idx=0;idx<A.length;idx++) newArr[A[idx]-1] = A[idx];
        
        for(int idx=0;idx<newArr.length;idx++)
            if(newArr[idx] == 0) val = idx+1;
            
        return val;
    }
}

 

결과

 

https://app.codility.com/demo/results/trainingUC926U-GP2/

 

시간복잡도(Detected time complexity) : O(N) or O(N * log(N))