[실리콘벨리 알고리즘 시리즈] 빠진 숫자 찾기 (Find the Missing Number) 파이썬 풀이

시작하며

미국의 네카라쿠배인 FAANG

개발자를 채용하는데 알고리즘 문제해결능력을 어느정도 볼것인가 대한 갑논을박이 있지만 좌우간 현재시점에서 알고리즘은 개발자를 뽑는 하나의 주된 척도로 사용하고 있습니다. 특히 오프라인 알고리즘 면접인 경우 쉬운 문제로 시작했지만 조건을 추가하거나 힌트를 주고 어떻게 최적화하는지 물어봅니다. 이런 연습을 하기 제일 좋은 것은 하나의 문제를 다양한 방법으로 풀어보고 최적화하는 것이라고 생각합니다.

실리콘벨리 알고리즘 시리즈는 쉬운 문제지만 다양한 각도로 풀어봅니다. 국내 IT기업, 실리콘벨리 문제 해설 저장소인 Github Brave Tech Interview에 코드 일부가 올라갑니다.

문제. 배열에 빠진 수 찾기(missing number)

서로 다른 [1, n]범위의 n-1개의 숫자가 들어있는 리스트가 주어집니다. 주어진 배열에 빠진 수를 찾으세요.

• 연관 문제
  • LeetCode. Missing Number
  • 백준 1920. 수 찾기

풀이 1. 완전탐색

가장 오래 걸리는 방법으로 생각해볼 수 있는 것은 완전탐색입니다. [1, N] 범위의 숫자를 하나씩 배열에 있는지 검사하는 방법입니다.

시간복잡도: O(n^2) 공간복잡도: O(1)

def find_missing_number_bruteforce(A):
    N = len(A)

    for cur in range(1, N+1):
        flag = False
        for a in A:
            if cur == a:
                flag = True; break

        if flag is False:
            print("Missing number is " + str(cur))
            break

풀이 2. 정렬

배열에 숫자가 있는지 하나씩 검사하는 방법을 정렬을 사용하면 조금 더 빠르게 할 수 있습니다. Complexity of Python Operations에 의하면 파이썬 내장함수 .sort의 시간복잡도를 O(nlogn)이라고 합니다.

시간복잡도: O(nlogn) 공간복잡도: O(1)

def find_missing_number_sort(A):
    A.sort()
    for cur in range(1, len(A)+1):
        if cur not in A:
            print("Missing number is " + str(cur))
            break

풀이 3. 해슁

해싱을 사용하면 시간복잡도를 줄일 수 있습니다. 파이썬 set의 조회 / 추가 / 삭제의 시간복잡도는 O(1)입니다. (참고. wiki.python.org)주어진 배열일 set으로 변환해주고 하나씩 숫자가 있는지 검사합니다.

시간복잡도: O(n) 공간복잡도: O(n)

def find_missing_number_hashing(A):
    A = set(A)

    for cur in range(1, len(A)+1):
        if cur not in A:
            print("Missing number is " + str(cur))
            break

풀이 4. 총합 공식(summation formula)

풀이 3의 공간복잡도를 1로 줄일 수 있는 방법이 있습니다. 과거 수열을 공부할때 연속된 수의 합을 구하는 총합 공식을 배웠을 것입니다. [1, N]의 총합에 현재 배열의 수를 빼면 배열에 없는 수가 나옵니다.

시간복잡도: O(n) 공간복잡도: O(1)

def find_missing_number_summation_formula(A):
    N = len(A)

    total_sum = (N + 1) * (N + 2) // 2
    curr_sum = sum(A)

    if total_sum - curr_sum != 0:
        print("Missing number is " + str(abs(total_sum - curr_sum)))

풀이 5. XOR

알고리즘을 생각할 때 수의 연산이 등장하면 기본적으로 수의 범위를 생각해야합니다. 풀이 4는 숫자가 커질 경우 정수 오버플로우(integer overflow) 문제가 발생할 수 있습니다.

XOR의 특징은 같은 수를 XOR 하면 0이 나온다는 것입니다. 서로 같은 수를 XOR 하게 되면 0이 나오고 0 또한 XOR 연산시 0이 됩니다. A3 ^ 0 은 A3이기에 최종적으로 배열에 없는 숫자인 A3를 찾을 수 있습니다.

시간복잡도: O(n) 공간복잡도: O(1)

def find_missing_number_xor(A):
    N = len(A)
    X1 = A[0]
    X2 = 0

    for i in range(1, N):
        X1 = X1 ^ A[i]
    for cur in range(1, N+2):
        X2 = X2 ^ cur

    print("Missing number is " + str(X1 ^ X2))

현직자가 해설해주는 기술면접이라는 주제로 Github Brave Tech Interview 를 운영하고 있습니다.
국내 IT 기업, 실리콘벨리 문제를 가장 빨리 만나보세요🚀