[codility] PermMissingElem : python

An array A consisting of N different integers is given.

# N개의 다른 정수로 구성된 배열 A 

 

The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

#배열은 1부터 N+1의 값을 포함한다. (1요소만 없음)

#목표는 없는 요소를 찾는것!

 

Write a function:

def solution(A)

 

that, given an array A, returns the value of the missing element.

#A가 주어졌을 떄 없어진 값을 반환하라.

 

For example, given array A such that:

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

the function should return 4, as it is the missing element.

#예를 들어 A가 [2,3,1,5] 일때 

# 함수는 4를 return 해주어야한다. ((N == 4+1 == 5이므로 1~5사이의 값,  이 중 4가 없으니 4리턴))

 

 

 Write an efficient algorithm for the following assumptions:

 

• N is an integer within the range [0..100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1..(N + 1)].

- N은 0부터 100000
- A의 요소는 전부 중복되지 않는다. 
- 각 요소는 1 ~ N+1 사이의 값이다. 

 

 

 

처음 생각했을 땐 A를 오름차순으로 정렬하면, 

인덱스가 0일 때 1 

1일 때 2 이런식으로 되다가 어느순간 안맞을 경우에 해당 인덱스 +1의 값이 정답이겠다 싶어서 코드를 작성해봤다. 

 

결과적으론  (50%)

def solution(A):
    A.sort()
    N = len(A) +1

    for i in range(N): # 5
        if A[i] != i+1:
           return i+1
           
    return N

 

결과를 보자마자 바보같은 방법으로 풀었다는걸 깨달았다. 

없는 수가 1개만 있으면 (1~N까지 다 더한값) -  (A의 요소를 전부 더한 값) 을 사용할 경우 없는 값이 나올텐데 ㅎㅎ

 

 

100%

def solution(A):
    N = len(A) +1
    A.sort()
    sum = 0
    for i in range(1,N+1):
        sum += i
    
    findsum = 0
    for i in A:
        findsum += i

    return sum - findsum

 

영어로 문제푸는건 처음인데 이제 좀 익숙해진것 같다.