Daily Coding Problem을 subscribe 하면 매일 한 개의 코딩 문제를 이메일로 받을 수 있다.

DCP #2

이 문제는 실제 우버(Uber) 면접에서 나온 질문이다.

주어진 정수의 배열로 새로운 배열을 만들려고 한다.
새로운 배열 i번째 원소에는, 기존 배열의 i번째 원소를 제외한 모든 값들의 곱이 저장되어 있다.

예를들어 [1, 2, 3, 4, 5] 배열이 주어졌을 때, 새로운 배열 [0]번째 원소에는 기존 배열의 1을 제외한 모든 값들의 곱(2 * 3 * 4 * 5)인 120의 값이 들어가게 된다.

입력: [1, 2, 3, 4, 5]
출력: [120, 60, 40, 30, 24]

보너스: 나누기 연산자를 사용할 수 없다면?

원문 읽기


코드 & 설명

C 코드 보기

나누기 사용 가능

모든 원소들의 곱을 구하고 배열을 돌면서 해당 원소의 값으로 나눠주면 된다.
새로운 배열을 만들지 않아도 되기때문에 추가적인 메모리 사용이 없다.

def with_div(arr)
    product = arr.inject(:*)
    n = arr.length
    for i in (0 ... n)
        arr[i] = product/arr[i]
    end
    arr
end

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

나누기 사용 불가능

나누기를 사용 할 수 없다?

첫 번째(이자 마지막) 방법은 이중 반복문을 사용 하는 것 이다.
배열을 돌면서 해당 원소와 다른 원소들의 값을 곱한 후 미자막에 새로운 배열에 저장한다.

계속해서 기존 배열의 값들을 사용해야 되기 때문에 새로운 배열을 만들어야 한다.

def without_div(arr)
    n = arr.length
    ans = []

    for i in (0 ... n)
        prod = 1
        for j in (0 ... n)
            if j != i
                prod *= arr[j]
            end
        end
        ans.insert(i, prod)
    end
    ans
end

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

아래는 루비식으로 짠 코드인데 사실 상 위 코드와 별반 다른게 없다.

def wo_division2(arr)
    n = arr.length
    ans = [] * n

    for i in (0 ... n)
        ans[i] = (arr - [arr[i]]).inject(:*)
    end
    ans
end

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

나누기 연산이 없을 때 도저히 O(n^2) 이하의 방법으로는 풀 방법을 떠올리지 못해서
찾아봤는데 역시 O(n)에 푸는게 가능하기는 한 것 같다.

블로그의 코멘트들을 보면 O(n)으로 푼 많은 코드들을 확인 할 수 있다.


Blog: https://muicode.github.io
DCP Github: https://github.com/muicode/DCP