Codility_PremMissingElem

3-2. PremMissingElem
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개의 서로 다른 정수로 구성된 배열 A가 주어지고 배열에는 [1…(N + 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) {
        int checkNum = 1;
        // A의 크기 +1은 배열 중 가장 큰 수
        for(int i = 1; i <= A.length + 1; i++){
            boolean found = false;
            for(int j = 0; j < A.length; j++){
                if(A[j] == checkNum){
                    found = true;
                    break;
                }
            }
            if(found){
                    checkNum++;
                }else{
                    return checkNum;
                }
        }
        return checkNum;
    }
}

for문을 통해 배열안에 1부터 A의 크기 더하기 1만큼 반복하면서
checkNum를 있는 수 일경우에는 +1하여 다음 숫자를 체크하는 방식으로 작성하였습니다.

해당 방식은 점수 퍼센트가 60%가 나와서 체크 해보니

타임아웃 에러가 발생합니다.

해시맵을 사용한 코드를 보고 코드를 수정한 코드->

// 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) {
        HashMap<Integer, String> map = new HashMap<>();
        for(int i = 1; i <= A.length + 1; i++)map.put(i,"true");
        for(int i : A)map.remove(i);
        return map.keySet().stream().findFirst().get();
    }
}

문제 풀어보기 -> https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/