Python3でCodilityのLessonを解いてみた

# はじめに
みなさん[Codility](https://app.codility.com/programmers/)知ってますか？
就職試験なんかでよく使われるコーディングテストのサイトで、[Lesson](https://app.codility.com/programmers/lessons/1-iterations/)として練習問題を解くこともできます。
Codilityでは過去の自分の提出を見ることができないので、メモ代わりにPythonで解いた自分の解答を載せていこうと思います。

## Lesson1 BinaryGap
https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

```
def solution(N):
    # write your code in Python 3.6
    binN = format(N, 'b')
    
    streak = 0
    max = 0
    
    for n in binN:
        if n=='1':
            if(streak > max):
                max = streak
            streak = 0
        else:
            streak += 1
    
    return max
```
Pythonでは組み込みのformatでint→2進数stringの変換ができるのでループとifが分かれば後は楽勝ですね。
中学数学なんかだと2で割っていって余りから2進数に変換とかしていた気がします。

## Lesson2 OddOccurrencesInArray
https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

```
def solution(A):
    # write your code in Python 3.6
    numSet = set()
    
    for a in A:
        if a in numSet:
            numSet.remove(a)
        else:
            numSet.add(a)
            
    for num in numSet:
        return num

```
PythonのSetを使いました。
Aの中の要素aを一つずつ取り出していって、もしnumSetにaがあればremoveして、numSetにaがないならaをaddします。これを続ければ最後には1回しかAの中に登場しない要素が残るのでそれをreturnします。

## Lesson2 CyclicRotation
https://app.codility.com/demo/results/trainingC2CJPS-6KP/

```
def solution(A, K):
    # write your code in Python 3.6
    length = len(A)
    list = []
    for i in range(length):
        index = cycleIndex(i,K,length)
        list.append(A[index])
    return list

def cycleIndex(i,K,length):
    if i-K < 0:
        return cycleIndex(length + i, K, length)
    else:
        return i-K
```
再帰を使って解きました。pythonのlistだと言語機能でA[-1]とかが参照できるので、条件式のところをi-K < -lengthにしたほうが再帰が一回少なくて済みますね(今気づいた)

## Lesson3 FrogJmp
https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/

```
def solution(X, Y, D):
    # write your code in Python 3.6
    dif = Y - X
    return -(-dif // D)
```
切り上げの割り算ができれば一発で解けますね。
C++なんかでよく使われる競技プログラミングのテクニックとしてa/bは(a + (b - 1)) / bとすれば切り上げの結果を求められるそうですがPythonなら-(-a//b)って書く方が綺麗だと思います。（個人的意見）

## Lesson3 PermMissingElem
https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

```
def solution(A):
    # write your code in Python 3.6
    list = []
    for a in A:
        list.append(a)
    list.sort()
    prev = 0
    for l in list:
        if l-prev!=1:
            return l-1
        prev = l
    return len(A)+1
```

## Lesson3 TapeEquilibrium
https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

```
def solution(A):
    # write your code in Python 3.6
    leftSum = 0
    rightSum = sum(A)
    
    length = len(A)
    
    min = 2000 * 100000 + 1
    
    for i in range(length-1):
        leftSum += A[i]
        rightSum -= A[i]
        
        if abs(leftSum - rightSum) < min:
            min = abs(leftSum-rightSum)
    
    return min
```
素直にループ回して最小値を求めました。
関係ないですがpythonってintに最大値がないのでsys.maxsizeより大きな数値もメモリが許せば扱えるらしいですね。
## Lesson4 FrogRiverOne
https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

```
def solution(X, A):
    # write your code in Python 3.6
    leafPos = set()
    count = 0
    result = 0
    for a in A:
        leafPos.add(a)
        if len(leafPos) == X:
            return count
        count += 1
    return -1
```
1~Xまでの数字が現れたかどうかをsetならlen()を使って判定できるのでO(N)で解けました。list使ってforぶん回して判定とかするとO(N**2)扱いでPerformanceが100％出ませんでした。

## Lesson4 MaxCounters
https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/
完答できず

## Lesson4　MissInteger
https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

```
def solution(A):
    # write your code in Python 3.6
    numSet = set()
    
    for a in A:
        if a > 0:
            numSet.add(a)
    
    for i in range(10000000):
        i = i+1
        if i in numSet:
            continue
        else:
            return i
```
0以下の値は問題に全く関係ないので除外して、後はAに含まれない最小値をreturnすればOK

## Lesson5 PassingCars
https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

```
def solution(A):
    # write your code in Python 3.6
    A.reverse()
    
    sum = 0
    suffixSum = 0
    for a in A:
        if a == 1:
            suffixSum += 1
        if a == 0:
            sum += suffixSum
    
    if sum > 1000000000:
        return -1
    else:
        return sum
```

## Lesson6 MaxProductOfThree

```
def solution(A):
    # write your code in Python 3.6
    A.sort()
    
    max1 = A[-1] * A[-2] * A[-3]
    max2 = A[0] * A[1] * A[-1]
    
    if max1 > max2:
        return max1
    else:
        return max2
```
(最小値,2番目に小さい値,最大値)か(最大値,2番目に大きい値,3番目に大きい値)の組み合わせのどちらかが最大値なことに気づけば解ける問題でした。

## Lesson6 Distinct
https://app.codility.com/programmers/lessons/6-sorting/distinct/

```
def solution(A):
    # write your code in Python 3.6
    numSet = set()
    
    for a in A:
        numSet.add(a)
    
    return len(numSet)
```
setは要素の重複を許さないのでsetに要素を追加してsetの要素を数えればOKです。

## Lesson6 Triangle
https://app.codility.com/programmers/lessons/6-sorting/triangle/

```
def solution(A):
    # write your code in Python 3.6
    A.sort()
    
    for i in range(1,len(A)-1):
        if A[i] + A[i-1] > A[i+1]:
            return 1
    
    return 0
```
ソート済みなら三角形の判定はO(N)でできます

## Lesson7 Brackets
https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

```
def solution(S):
    # write your code in Python 3.6
    
    stack = []
    
    for s in S:
        if s == ')':
            if len(stack) == 0:
                return 0
            c = stack.pop()
            if c =='(':
                continue
            else:
                return 0
        
        elif s == ']':
            if len(stack) == 0:
                return 0
            c = stack.pop()
            if c == '[':
                continue
            else:
                return 0
        
        elif s == '}':
            if len(stack) == 0:
                return 0
            c = stack.pop()
            if c == '{':
                continue
            else:
                return 0
        
        else:
            stack.append(s)
    if len(stack) == 0:
        return 1
    else:
        return 0
```
スタックをちゃんと理解できているかの問題でした。

## Lesson7 Fish
https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

```

```

## Lesson7 Nesting
https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/

```
```

## Lesson7 StoneWall
https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

```
```

## Lesson8 Dominator
https://app.codility.com/programmers/lessons/8-leader/dominator/

```
```

## Lesson8 EquiLeader
https://app.codility.com/programmers/lessons/8-leader/equi_leader/

```
```

## Lesson9 MaxProfit
https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

```
```

## Lesson9 MaxSliceSum
https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/

```
```

## Lesson9 MaxDoubleSliceSum
https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

```
```

## Lesson10 CountFactors
https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/count_factors/

```
```