[Codility] MissingInteger

MissingInteger

1차 시도

def solution(A):
    # write your code in Python 3.6
    A = sorted(A)
    #print(A)
    idx = binary_search(A, 0, 0, len(A)-1)
    A = A[idx:]
    #print(A)
    if len(A) == 0:
        return 1
    if A[0] == 2:
        return 1
    for i in range(idx+1, len(A)):
        if A[i] - A[i-1] == 2:
            return A[i] - 1
    return A[len(A)-1] + 1
    #pass

def binary_search(arr, val, start, end):
    if start == end:
        if arr[start] > val:
            return start
        else:
            return start+1
 
    # this occurs if we are moving
    # beyond left's boundary meaning
    # the left boundary is the least
    # position to find a number greater than val
    if start > end:
        return start
 
    mid = (start+end)//2
    if arr[mid] < val:
        return binary_search(arr, val, mid+1, end)
    elif arr[mid] > val:
        return binary_search(arr, val, start, mid-1)
    else:
        return mid

쓰읍.. performance는 괜찮은데 로직이 틀린듯
그래도 컴파일 에러 나는 실수는 안하니까 다행이라고 할 수 있겠다

2차 시도

def solution(A):
    # write your code in Python 3.6
    A = sorted(A)
    #print(A)
    idx = binary_search(A, 0, 0, len(A)-1)
    A = A[idx:]
    #print(A)
    if len(A) == 0:
        return 1
    if A[0] != 1:
        return 1
    for i in range(1, len(A)):
        if A[i] - A[i-1] >= 2:
            return A[i-1] + 1
    return A[len(A)-1] + 1
    #pass

def binary_search(arr, val, start, end):
    if start == end:
        if arr[start] > val:
            return start
        else:
            return start+1
 
    # this occurs if we are moving
    # beyond left's boundary meaning
    # the left boundary is the least
    # position to find a number greater than val
    if start > end:
        return start
 
    mid = (start+end)//2
    if arr[mid] < val:
        return binary_search(arr, val, mid+1, end)
    elif arr[mid] > val:
        return binary_search(arr, val, start, mid-1)
    else:
        return mid

문제를 제대로 읽자!..
어디에도 연속적인 숫자라고 안써있었는데 착각해서
연속적인 숫자 사이에 빠진 숫자를 찾는 줄..
[94, 95, 96] 이런 인풋도 된다

복잡도는 잘 나오는데 또 틀림 흑흑 이번엔 1의 늪에 빠짐

0을 찾고 자르니까 이렇게 0이 여러개 있는 경우를 잡아내지 못하는구나! 잡았다 요놈
이제 진짜 다맞을 수 있음

3차 시도

우와 성공~!

def solution(A):
    # write your code in Python 3.6
    A = sorted(A)
    #print(A)
    idx = binary_search(A, 0, 0, len(A)-1)
    A = A[idx:]
    #print(A)
    if len(A) == 0:
        return 1
    if A[0] != 1 and A[0] != 0:
        return 1
    for i in range(1, len(A)):
        if A[i] - A[i-1] >= 2:
            return A[i-1] + 1
    return A[len(A)-1] + 1
    #pass

def binary_search(arr, val, start, end):
    if start == end:
        if arr[start] > val:
            return start
        else:
            return start+1
 
    # this occurs if we are moving
    # beyond left's boundary meaning
    # the left boundary is the least
    # position to find a number greater than val
    if start > end:
        return start
 
    mid = (start+end)//2
    if arr[mid] < val:
        return binary_search(arr, val, mid+1, end)
    elif arr[mid] > val:
        return binary_search(arr, val, start, mid-1)
    else:
        return mid