[hackerrank] Missing Numbers python

 

이전 문제와 같이 해시테이블 즉, python dictionary를 이용해보았다.

 

dictionary에서 주로 key in dict 이렇게 key값이 있는지 판별하는 in은 dictionary에서 시간 복잡도가 O(1)이다. (문제 키포인트)

 

1. 우선 arr, brr의 value들을 key값으로, 갯수를 value로 하는 dictionary를 각각 만들고

 

2. brr[i] in arrDic으로 빠진 것들을 찾아준다.

 

3. 빠진것들을 answerList에 append해주고 중복을 제거한뒤 sort해준다.

 

 

*아쉬운점 answerList에 중복된 수가 발생된다는것, 중복된 원소가 빠졋을때 그만큼 더 연산을 하는것 ...

def missingNumbers(arr, brr):
    # Write your code here
    arrDic = dict()
    brrDic = dict()
    answerList = list()
    for a in arr:
        if a in arrDic:
            arrDic[a] += 1
        else:
            arrDic[a] = 1
            
    for b in brr:
        if b in brrDic:
            brrDic[b] += 1
        else:
            brrDic[b] = 1
    
    for i in range(len(brr)):
        if brr[i] in arrDic:
            if brrDic[brr[i]] != arrDic[brr[i]]:
                answerList.append(brr[i])
            continue
        else:
            answerList.append(brr[i])
    answerList = list(set(answerList))
    answerList.sort()
    return answerList

 

아래코드는 조금 더 pythonic하고 깔끔하며, 군더더기 없는 코드를 찾아 보았다.

(출처: https://github.com/Murillo/Hackerrank-Problem-Solving/blob/master/Algorithms/Search/missing-numbers.py)

# Complete the missingNumbers function below.
def missingNumbers(arr, brr):
    m = max(arr + brr) + 1
    list = [0 for _ in range(m)]
    for i in arr:
        list[i] += 1
    for i in brr:
        list[i] -= 1
    return sorted([item for item in range(len(list)) if list[item] != 0])