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
그래서 결론은...?
와... 생각없이 썼다고 가차없이 에러가 뿜뿜이다.
에러를 살펴보자면...
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
아니 왜 틀렸지...? 분명 빈 배열 테스트를 했는데?
알고보니 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)) 이 나온걸 알 수 있다.
