[Codility] Lesson4. PermCheck - 문제풀이

Description

주어진 배열의 요소가 1~N까지 요소를 모두 가진 순열인지 여부를 반환하는 문제입니다.

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:

class Solution { public int solution(int[] 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.

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..1,000,000,000].

Solution 1. 정렬(Sort)

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

정렬 한 후 배열의 요소가 index+1과 일치 하지 않으면 빠진 순열이 있으므로 0을 반환해줍니다.

Reference

PermCheck coding task - Learn to Code - Codility