Lesson 4. Counting Elements - PermCheck

1. 문제

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

vector A에 1부터 N까지 값이 순서대로 있는지 확인하는 문제.

순서대로 있다면, return 1

값이 빠졌다면, return 0

 

예제1) return 1

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

 

예제2) return 0

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

 

 

2. 매개변수 조건

• vector A 크기 : 1 ~ 100,000
• vector A 요소 값 범위 : 1 ~ 1,000,000,000

 

3. 풀이 전략

vector A를 오름차순으로 정렬 후, 빠진 값이 있는지 1부터 확인한다.

 

 

4. 코드 (C++)

#include <algorithm>

int solution(vector<int> &A) {

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

    return 1;
}