[Codility] Lesson 3 : PermMissingElem - JAVA

문제

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–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(int[] A)에 입력되는 배열 A는 N개의 Element를 가지고 있고,  N 범위는 1 ~ 100,000이다.
배열 A에는 1부터 N+1까지의 연속된 숫자를 가지고 있다.
이때 연속된 숫자 중 누락된 숫자를 찾아 반환한다.

예를 들어

        A[0] = 2
        A[1] = 3
        A[2] = 1
        A[3] = 5

일 때, 연속된 숫자 중 누락된 숫자는 4인 것을 알 수 있으며, 이 값을 반환해주면 된다.

 

풀이 - 1

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        int result = 0;
        Arrays.sort(A);
        for(int i=0; i<A.length; i++) {
            if(A[i] != (i+1)) {
                result = i+1;
                break;
            }
        }
        return result;
    }
}

 

'풀이 - 1'에 대한 회고

 

먼저 배열을 정렬한 후 반복문을 통해 A[i] 값이 i+1과 같이 않으면 누락된 것으로 생각하고

i+1 값을 반환하였다.

정렬을 했기 때문에 누락된 숫자 이후의 값들은 굳이 비교할 필요가 없다고 생각했다.

그러나 결과는...

 

 

퍼포먼스도 문제인데 정확도가 최악!

알고리즘을 풀기만 했다.

조금 더 생각을 해서 효율적인 소스코드를 작성해봐야겠다.

 

풀이 - 2

import java.util.HashSet;
class Solution {
    public int solution(int[] A) {
        HashSet<Integer> iSet = new HashSet<Integer>();
        for(int i=1; i<=A.length+1; i++) {
            iSet.add(i);
        }
        for(int i=0; i<A.length; i++) {
            if(iSet.contains(A[i])) iSet.remove(A[i]);
        }
        return iSet.iterator().next();
    }
}

 

'풀이 -2'에 대한 회고

 

두 번째 방법으로 차집합을 생각했다.

A가 배열이 아니라 List나 Set이었다면 removeAll()을 통해 바로 차집합을 구하려고 했지만

배열을 굳이 List로 바꾸면 효율적이지 않을 것 같아서 Set의 데이터를 지워주기로 했다.

 

먼저 Set에 1부터 A.lenth + 1까지의 숫자를 넣고

반복문을 통해 배열 A의 값이 Set에 있으면 지워주었다.

그 결과 Set에는 배열 A에서 누락된 숫자 하나만 남게되고 이 값을 반환해주면 끝!

 

 

정확도와 퍼포먼스도 잘 나온다.

 

 

그리고 시간복잡도도 나쁘지는 않다!

 

다른 사람의 풀이

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        for(int i=0; i<A.length; i++) {
            if(i+1 != A[i]) return i+1;
        }
        return A.length+1;
    }
}

 

'다른 사람의 풀이'를 통한 회고

 

다른 사람의 풀이를 보고 '풀이 - 1'을 다시 봤다.

역시 '풀이 - 1'을 작성할 때의 생각이 틀리지는 않았다.

다만, 다른 사람들은 배열이 비어있는 경우 또는 N+1의 값이 누락된 경우를 생각해서 코드를 작성하였지만

나의 '풀이 - 1'에는 그런 생각이 고려되지 않았다.

그리고 반환해주기 위해 쓸데없이 result라는 변수를 사용하기도 했고!

 

 

문제를 잘 읽고 그런 부분만 작성했더라면 나도 '다른 사람의 코드'처러 정확도와 퍼포먼스가 나왔겠지?

문제를 조금 더 자세히 읽고, 고민하고, 필요한 경우 방어코딩도 잘 해야겠다.

참고로 '다른 사람의 코드'도 '풀이 - 2'와 같은 시간 복잡도가 나온다.