PermCheck

🔗 문제 링크

https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/start/

❔ 문제 설명

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

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

is a permutation, but array A such that:

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

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

def solution(A)

that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

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

the function should return 1.

Given array A such that:

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

the function should return 0.

⚠️ 제한사항

• N is an integer within the range [1..100,000];

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

---

💡 풀이 (언어 : Java)

정렬하고 해당 위치의 수가 아니면 바로 0을 리턴하고, 반복문을 빠져나오는데 성공하면 수열이 올바르게 존재하는 것이므로 1을 리턴한다. 시간 복잡도는 $O(N)$ or $O(N * log(N))$

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 0;
        }
        return 1;
    }
}