[Codility4/Lesson]MissingInteger (python)

• 리스트 안에 없는 가장 "작은" 양수를 반환하는 것이다
• 범위 안에서 가장 작은 값이 아니라 그냥 작은 양수를 반환하는 것이다
• 만일 리스트 안에 양수가 없으면 1을 반환

삽질의 현장 함께 해봅시다

| 1트

def solution(A):

    max_num = 0

    for i in A:
        max_num = max(max_num, i)
    
    compare_set = set([i for i in range(1, max_num + 1)])
    a_set = set(A)

    compare_list = list(compare_set - a_set)
    if compare_list:
        return max(compare_list)
    elif max_num > 0:
        return max_num + 1
    else:
        return 1 

• 맨 처음 문제를 잘못 이해해서 없는 양수중 가장 작은 값이 아니라 큰 값을 구함
• set 을 두개 만들고 set 끼리 빼는 방식을 선택함

결과는 여기에

| 2트

def solution(A):

    max_num = 0
    for i in A:
        max_num = max(max_num, i)
    
    compare_set = set([i for i in range(1, max_num + 1)])
    a_set = set(A)

    compare_list = list(compare_set - a_set)
    if compare_list:
        return min(compare_list)
    elif max_num > 0:
        return max_num + 1
    else:
        return 1 
 

• 그래서 작은 값을 반환하도록 하고 set끼리 빼도록 함
• 그랬더니 느리다고 함

결과는 여기에

| 3트

def solution(A):

    max_num = 0
    for i in A:
        max_num = max(max_num, i)
    
    compare_set = set([i for i in range(1, max_num + 1)])
    a_set = set(A)

    compare_list = sorted(list(compare_set - a_set))
    
    if compare_list:
        return compare_list[0]
    elif max_num > 0:
        return max_num + 1
    else:
        return 1 
 

• 혹시 compare_list에서 min값을 구하는게 느린게 아니었을까 하고 min 대신 정렬을 쓰고 첫번째 값을 반환하도록 함
• (근데 이게 더 느리지 않나?)

결과는 여기에

| 4트

def solution(A):

    sorted_A = sorted(A)
    length_A = len(A)

    for i, num in enumerate(sorted_A):
        if i+1 < length_A:
            if sorted_A[i+1] > num + 1:
                if num + 1 > 0:
                    return num + 1

    if sorted_A[0] >= 1:
        return sorted_A.pop() + 1 
    else:
        return 1 
        

• 초장부터 잘못됐음을 깨닫고 갈아 엎음
• list 길이가 1개일 경우 측정을 못하는 방식

결과는 여기에

| 5트

def solution(A):

    sorted_A = sorted(A)
    length_A = len(A)
    if length_A == 1 and A[0] != 1:
        return 1

    for i, num in enumerate(sorted_A):
        if i+1 < length_A:
            if sorted_A[i+1] > num + 1:
                if num + 1 > 0:
                    return num + 1

    if sorted_A[0] >= 1:
        return sorted_A.pop() + 1 
    else:
        return 1 
        

• 그래서 list 길이가 하나일 경우에 대한 처리를 해줌
• 근데 죄다 1을 반환하는 것이 정답인 것을 보고 쎄함을 느낌
• 알고보니 난 범위 안에서 가장 작은 값을 구하고 있던 것...(list에 나온 범위가 아니라 1부터 max값의 범위이다)
• 멍청이

결과는 여기에

| 6트

import collections

def solution(A):
    max_num = -1
    count_dict = collections.defaultdict(int)

    for i in A:
        max_num = max(i, max_num)
        count_dict[i] += 1
    
    for j in range(1, max_num + 1):
        if count_dict[j] == 0:
            return j

    if max_num <= 0:
        return 1
    else:
        return max_num + 1
        

• 1 ~ max값까지를 비교해서 중간에 빠진 값 중 첫번째에 return 하도록 함
• 만일 다 있다면 max값 + 1
• 만일 다 음수이면 return 1

결과는 여기에

---

멍청이...

• 하지만 얻은 교훈은 set끼리 빼는 방식을 생각하면 느리다
• 그리고 전체를 구하는 것 보다는 값이 나오면 바로 return 하는 방식이 더 빠르다