Codility: PermCheck (Python)

주제

Lesson 4: Counting Elements

 

난이도

Easy

 

문제

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:
def solution(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].

 

주어진 배열 A가 순열이면 1, 아니면 0을 반환한다.

여기서 순열의 정의는 1부터 N(배열의 크기)까지 하나씩, 모두 나오는 경우를 말한다.

조건은 배열 A의 크기 N이 1~100,000이며, A의 각각의 원소는 1~1,000,000,000이다. 

또한 efficient해야한다.

 

풀이

efficient하게 풀라길래 최대한 단순하게 생각하려고 많이 노력했다.

일단 순열에서 중요한 조건은 중복이 되지 않고, 각각의 값이 다 하나씩 존재해야한다는 점이다.

 

1. list A를 set으로 변경한 후의 길이와 list A의 길이를 비교해서 다르면 순열이 아니다.

-> list를 set으로 변경하면 중복된 원소가 사라진다. 즉, 만약 list A에 중복된 원소가 있다면 set(A)의 크기와 list A의 크기는 다를 것이다. 중복값이 있다면 순열이 아니므로, 0을 반환한다.

 

2. A의 최대값(max_num)을 구한다.

 

3. list A의 길이와 max_num이 다르면 순열이 아니다.

-> 1번에서 중복이 있는 list는 걸렀기 때문에 여기에 온 list A는 중복 원소가 없다. 중복이 없다면, 순열인 경우에 해당 리스트의 최대값을 N이라고 했을 때, 순열에는 순서 상관없이 1~N값이 존재할 것이고 따라서 해당 list의 길이는 당연히 N이 될 것이다. 만약 길이와 최대값 max_num이 다르다면 중간에 특정 값이 빠진 것으로 해석할 수 있다.

 

Ex. A = [1,2,4]

max_num = 4, len(A) = 3

 

코드

def solution(A):
    # if there is duplicate element, A isn't permutation
    # check only once condition
    if len(set(A)) != len(A):
        return 0

    # if the list length is smaller than max number in list,
    # some element is missing. (= A isn't permutation)
    # check each element exist
    max_num = max(A)
    if len(A) != max_num:
        return 0
    else:
        return 1

 

 

시간복잡도

len() : O(1)

max() : O(N)

 

따라서 O(N)의 시간복잡도를 갖는다.

 

 

결과

codility 결과