Codility - Perm Check // C++

문제

 

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:

int solution(vector<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].

N 크기로 주어진 벡터가 순열로 이루어져있는지 확인하고, 맞다면 1을 아니라면 0을 반환하는 함수를 작성하라.

---

 

풀이

 

N 크기의 순열이라면 1 ~ N이 각각 한 번씩 나오는 것을 의미하므로, 오름차순으로 정렬 후 1씩 증가시키며 비교하여 다르다면 0을 같다면 1을 반환하였다.

 

---

 

코드

#include <algorithm>

int solution(vector<int> &A) {
    sort(A.begin(),A.end());
    
    for(int i=0;i<A.size();i++){
        if(A[i] != i+1)
            return 0;
    }
    
    return 1;
}