[Codility] PermMissingElem 30→80→100

문제출처 : https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

문제요약 :  배열안에 여러개의 정렬되지 않은 숫자(1, n+1, ...)가 있다

               여기서 빠진 요소 하나를 반환해라.

               -숫자범위는 0~100000

              - 중복된 숫자는 제거해라

                   

               

[30점]

https://app.codility.com/demo/results/trainingSCGD52-MA7/

문제의도를 아얘 잘못 파악했다..

import java.util.*;
 
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
 
class Solution {
    public int solution(int[] A) {
      if(A.length<=1) {
            return 1;
        }
 
        int[] arr = Arrays
                .stream(A)
                .distinct()
                .sorted()
                .toArray();
 
        int result = 0;
        for(int i=0; i<arr.length-1;i++){
            if(arr[i]+1 != arr[i+1]){
                result = arr[i]+1;
                break;
            }
        }
 
        return result;
    }
}

[80점]

https://app.codility.com/demo/results/training4BHC5Z-BA3/

정답은 맞았지만 time out이 나와버린 케이스

//you can also use imports, for example:
 import java.util.*;
 
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
 
class Solution {
    public int solution(int[] A) {
       int[] arr = Arrays
                .stream(A)
                .sorted()
                .toArray();
 
        for(int i=0; i<arr.length; i++){
            if(arr[i] != i+1) return i+1;
        }
        return arr.length+1;
    }
}

[100점]

https://app.codility.com/demo/results/trainingJ2AGG3-TXM/

위의 속도개선을 위해 Stream을 제거하였다.

TC중 숫자의 범위가 ~10000이고 

Stream을 사용했을때 0.12초

Arrays.sort를 사용했을 때 0.032초가 걸렸다..

TC가 ~100000일 경우는

Stream은 0.268초

Arrays.sort는  0.172초가 걸렸다.

괜히 Stream써서 해보려고했다가 낭패봤다 ㅎㅎㅎ..

                             

import java.util.Arrays;
 
public class Main {
 
    public static void main(String[] args) {
 
        int[] A={1,2,4};
        System.out.println(solution(A));
    }
 
    public static int solution(int[] A) {
        Arrays.sort(A);
 
        for(int i=0; i<A.length; i++){
            if(A[i] != i+1) return i+1;
        }
 
        return A.length+1;
    }
}