PermMissingElem

🔗 문제 링크

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/start/

❔ 문제 설명

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:

def solution(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.

⚠️ 제한사항

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

---

💡 풀이 (언어 : Java)

우선 정렬을 해야 최대한 빠르고 단순하게 빠진 수를 찾을 수 있다. 수가 1씩 증가하는 반복문인덱스 + 1의 값이 아닌 수가 발견되면 바로 정답이다. 만약 반복문을 다 돌고도 찾지 못하면 모든 원소가 차례대로 존재하는 것이므로 바로 나올 다음 수 = 길이 + 1이 정답이다.

Java

import java.util.Arrays;

class Solution {
    public 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;
    }
}