[Algorithm] Codility Lesson 4 Counting Elements - PermCheck

정수 N개로 구성된 비어있지 않은 배열 A가 주어진다.

permutation이란 1부터 N까지 각 요소를 단 한 번만 포함하는 숫자들이다.

예를들어 배열 A가 다음과 같다면:

A[0] = 4

A[1] = 1

A[2] = 3

A[3] = 2

permutation이다. 하지만 배열 A가 다음과 같다면:

A[0] = 4

A[1] = 1

A[2] = 3

permutation이 아니다. 왜냐하면 2가 빠졌기 때문이다.

목표는 배열 A가 permutation인지 아닌지 확인하는 것이다.

함수 작성:

class Solution { public int solution(int[] A); }

배열 A가 주어지고, 배열 A가 permutation이라면 1을 리턴 아니면 0을 리턴한다.

예를들어 배열 A가 다음과 같다면

A[0] = 4

A[1] = 1

A[2] = 3

A[3] = 2

함수는 1을 리턴해야한다.

배열 A가 다음과 같다면:

A[0] = 4

A[1] = 1

A[2] = 3

함수는 0을 리턴해야한다.

가정:

N은 [1..100,000] 범위의 정수이다.

배열 A의 각 요소는 [1..1,000,000,000] 범위의 정수이다.

복잡도:

최악의 시간복잡도는 O(N);

최악의 공간복잡도는 O(N) (입력공간 제외)

입력 배열의 요소는 수정할 수 있다.

https://codility.com/demo/results/trainingWXN3W6-5WB/