문제

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

N개의 서로 다른 정수로 구성된 배열 A 가 주어지는데

[1~ (N+1)] 범위의 원소가 있고 딱 한 개의 원소만 빠져있다.

이 빠진 숫자를 찾아서 리턴하는 문제

풀이

60점 짜리 댕댕코드

def solution(A):
    if len(A) == 0:
        return 1
    A.sort()
    for i in range(len(A) - 1):
        if A[i] + 1 != A[i+1]:
            return A[i] + 1
    return A[-1] + 1

저번에 배열이 비어있을 때 예외 처리 안 하면 점수를 깎는 함정이 있었으니 일단 해주고

A를 정렬한 다음 반복문으로 연속되지 않는 코드를 찾았는데 60점만 받았다.

만점 코드

등차수열 합 공식이 있는데

1부터 K 까지 의 합 은

🏫

sum = (K * (K + 1)) / 2

라는 공식이 있다.

그래서 1부터 N+1 까지 의 합 과

실제 A 배열의 총 합 을 빼주면

누락된 숫자를 찾을 수 있다.

def solution(A):
    N = len(A)
    total = (N + 1) * (N + 2) // 2  # 1부터 N+1까지의 합
    actual = sum(A)  # 배열의 실제 합
    return total - actual  # 누락된 숫자 반환

쉬워보인다고 거품물고 호다닥 풀면 항상 함정이나 감점이 있다...