[Codility]MissingInteger

This is a demo task.

Write a function:

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

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000].

 

1. 첫번째 시도 

   주어진 수 들의 갭차이를 구하고 중간에 빠진수가 있으면 리턴하고 아니면 제일 큰값의 +1 을 리턴하라고 판단하고 짬...

 

// 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) {
        // write your code in Java SE 8
        int returnValue = 0;
        int preValue = 0;
        int nextValue = 0;
        int gapValue = 0;

        TreeSet<Integer> treeSet = new TreeSet<>();
        for(int i:A){
            treeSet.add(i);
        }

        ArrayList<Integer> list = new ArrayList<>();

        Iterator ite = treeSet.iterator();
		while(ite.hasNext()){
            list.add(Integer.parseInt(ite.next().toString()));
        }

        for(int j=0 ; j < list.size() ; j++){
            if(j==0){
                preValue = list.get(j);
            }else if(j == 1){
                nextValue = list.get(j);
                gapValue = nextValue - preValue;
                if(j == list.size()-1){
                    returnValue = nextValue + gapValue;
                }
            }else if(j>1){
                preValue = list.get(j-1);
                nextValue = list.get(j);
                if(gapValue < nextValue - preValue){
                    returnValue = nextValue - gapValue;
                }else if(j == list.size()-1){
                    returnValue = nextValue + gapValue;
                }
            }
        }
        return returnValue;
    }
    
}

 

결과는...

 

예시 데이터 빼고 전부 실패...

 

2. 두번째 시도

 

// 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) {
        // write your code in Java SE 8

        TreeSet<Integer> treeSet = new TreeSet<Integer>();
        for(int i:A){
            treeSet.add(i);
        }

        int num = 1;

        while(treeSet.contains(num)){
            num++;
        }
        return num;
    }
    
}

 

결과는...

 

 

 

퍼포먼스 부분이 모자라서 77% 가 나왔다...

 

3.최종적으로 수정~!

 

// 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) {
        // write your code in Java SE 8

        HashSet<Integer> hashSet = new HashSet<Integer>();
        for(int i:A){
            hashSet.add(i);
        }

        int num = 1;

        while(hashSet.contains(num)){
            num++;
        }
        return num;
    }
    
}

 

TreeSet - > HashSet 으로 변경하니 퍼포먼스 해결~!