[Codility Lesson4] PermCheck

문제 : PermCheck

Test results - Codility

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

 

 

나의 풀이

- Score 100% , O(N) or O(N * log(N))

- 배열 A를 정렬한 후 인덱스+1 값과 같은지 확인

배열 A의 범위가 커서 이 방법으로 시간초과가 날 줄 알았는데 나지 않았다. (N의 범위가 100,000까지여서 그런 것 같다)

def solution(A):
    A.sort()
    for i in range(len(A)):
        if A[i]!=i+1:
            return 0
    return 1

 

 

다른 풀이

O(N) or O(N * log(N))

def solution(A):
    if max(A) != len(A) or len(set(A)) != len(A):
        return 0
    return 1

- 길이 비교로 바로 정답 유무 확인 가능한 방법