[Codility] 4. Counting Elements

4.1 FrogRiverOne

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

Write a function that, given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.
If the frog is never able to jump to the other side of the river, the function should return −1.

 

작은 개구리가 강의 다른 쪽으로 가고 싶어합니다. 그 개구리는 처음에 강의 한쪽 둑에 위치하고 (위치 0) 반대쪽 둑으로 가고 싶어합니다 (위치 X+1). 나뭇잎들이 나무에서 강의 표면으로 떨어집니다.

당신에게는 떨어지는 잎들을 나타내는 N개의 정수로 구성된 배열 A가 주어집니다. A[K]는 초 단위로 측정된 시간 K에서 하나의 잎이 떨어지는 위치를 나타냅니다.

목표는 개구리가 강 건너편으로 점프할 수 있는 가장 빠른 시간을 찾는 것입니다. 개구리는 1에서 X까지의 강 건너편 모든 위치에 나뭇잎이 나타날 때만 건너갈 수 있습니다. 즉, 우리는 1에서 X까지의 모든 위치가 나뭇잎으로 덮여 있는 가장 빠른 순간을 찾고 싶습니다. 여러분은 강에 흐르는 물의 속도가 무시할 정도로 작다고 가정할 수 있습니다. 즉, 나뭇잎이 강에 떨어지면 위치가 바뀌지 않습니다.

N개의 정수와 X개의 정수로 구성된 비어 있지 않은 배열 A가 주어졌을 때, 개구리가 강 반대편으로 점프할 수 있는 가장 빠른 시간을 되돌려 주는 함수를 쓰시오.

개구리가 절대로 강 반대편으로 점프할 수 없다면 함수는 -1로 되돌아가야 합니다.

def solution(X, A):
    rlist= [0] * X
    etime = 0
    for i, a in enumerate(A):
        if rlist[a-1] != 1:
            rlist[a-1] = 1
            etime+=1
        if etime == X:
            return i
    return -1

4.2 PermCheck

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.
The goal is to check whether array A is a permutation.

Write a function that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

 

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다.
순열은 1부터 N까지의 각 원소를 한 번, 한 번만 포함하는 수열입니다.
A 배열이 순열인지 확인하는 것이 목표입니다.

배열 A가 주어지면 배열 A가 순열이면 1을 반환하고 그렇지 않으면 0을 반환하는 함수를 쓰시오.

def solution(A):
    permutation = [0]*len(A)
    for a in A:
        if a-1 < len(permutation) and permutation[a-1] != 1:
            permutation[a-1] = 1
        else:
            return 0
    if sum(permutation) == len(A):
        return 1
    else:
        return 0