Codility Lesson 3 PermMissing Elem 나만의 풀이

문제

An array A consisting of N different integers is given. 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.

Write a function:

class Solution { public int solution(int[] A); }

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

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.

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)].

 

 

대충 해석하자면 배열 A에 N개의 각각 다른 정수가 주어지는데 A의 범위는 1부터 N+1까지의 범위이다

A의 리스트에서 중간에 빠진 요소를 찾아 리턴하라 라는 뜻이다.

당연스럽게 들어간 효율적으로 짜라는 것

 

 

첫번째 시도

효율을 생각해서 리스트가 아닌 딕셔너리로 A의 요소를 B의 key로 넣어 서칭에 강점인 해쉬테이블을 사용했다.

def solution(A):
    B = {}
    
    for i in A:
        B[i] = 0
    
    for i in range(1, len(A)+1):
        if i not in B:
            return i

 

그래서 결론은...?

 

50점대 코드

와... 생각없이 썼다고 가차없이 에러가 뿜뿜이다.

에러를 살펴보자면... 

 

1. 빈 배열 문제

empty_and_single

2. 요소가 한개이거나 2개일때의 문제

single, double

3. 범위를 N+1개를 지정해야 하는데 N개를 지정해서 틀린 문제

missing_first_or_last, large_range

 

 

두번째 시도

먼저 빈 배열과 요소 개수문제를 한번에 묶어 3개 이하의 제약을 걸었다.

그리고 A의 len이 0이라면 해쉬테이블을 쓸 필요가 없으므로 1 이상만 딕셔너리를 만들도록 지정하고 실행!

 

멋 없게 보인다면 당연하다. 생각하기 귀찮아서 대충 짠 코드이기 때문이지...

def solution(A):
    B = {}
    
    if len(A)>=1:
        for i in A:
            B[i] = 0

    if len(A)<3:
        if len(A)==0:
            return 0
        if len(A)==1:
            for i in range(1, 3):
                if i not in B:
                    return i    
    
    for i in range(1, len(A)+2):
        if i not in B:
            return i

90점

아니 왜 틀렸지...? 분명 빈 배열 테스트를 했는데?

알고보니 return 1을 해줘야 하는데 아무 생각없이 0으로 해서 틀렸다고 나왔다.

 

 

세번째 시도

return값을 1로 바꾸고 실행!

def solution(A):
    B = {}
    
    if len(A)>=1:
        for i in A:
            B[i] = 0

    if len(A)<3:
        if len(A)==0:
            return 1
        if len(A)==1:
            for i in range(1, 3):
                if i not in B:
                    return i    
    
    for i in range(1, len(A)+2):
        if i not in B:
            return i

100점!

 

바로 해쉬테이블을 써서 그런지 시간복잡도는 O(N) or O(N*log(N)) 이 나온걸 알 수 있다.

시간복잡도