# PermCheck 코딜리티 레슨 문제

코딜리티 레슨 문제

입력 받은 배열이 순열인지 아닌지를 판단하는 문제다.

A non-empty zero-indexed 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.

해당 문제의 원문이고, 몇가지 가정 사항이 있다. 순열은 1~N(배열크기)의 범위를 가지며 각 배열에 있는 원소들은 1~10억 까지의 범위를 갖는다.

문제 자체는 크게 어렵지 않아 생각 나는대로 구현했다. 시간복잡도는 O(N) 이다.

1 2 3 4 5 6 7 8 9 10 11 12

int solution(vector<int> &A){ int arrSize = A.size(); int isDuplicate[arrSize+1]; for(int idx = 1; idx < arrSize+1; idx++) isDuplicate[idx] = 0; for(int idx = 0; idx < arrSize; idx++){ if(A[idx] > arrSize) return 0; else isDuplicate[A[idx]]++; if(isDuplicate[A[idx]] >= 2) return 0; } return 1; }