Blind 75 | Product of Array Except Self (Array 6 / 8)

https://leetcode.com/problems/product-of-array-except-self

Product of Array Except Self - LeetCode

 

Product of Array Except Self - 자신을 제외한 모든 값의 곱 (?)

 

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

nums 정수 배열이 주어졌을 때 자신을 제외한 모든 요소들의 값인 배열 answer를 리턴하라.

모든 곱은 32 비트 정수 미만이다.

알고리즘은 O(n)이 소모되야 하며 나누기를 쓸 수 없다.

 

 

개요

 

언뜻 봤을 때는 간단해 보이는 문제지만 나누기를 쓸 수 없고 O(n)이란 시간제한 때문에 간단한 방법으로 풀 수 없다. 만약 시간제한이 걸려 있지 않다면 단순히 for 문을 두 번 돌려도 풀 수 있었을 테고, 나누기를 쓸 수 있었다면 정수들을 전부 곱한 뒤 루프를 한번 더 돌려 자신의 값만큼만 나누면 쉽게 풀 수 있었을 것이다.

 

답은 prefix와 postfix의 개념을 이용하면 풀 수 있다. Prefix Sum이란 알고리즘의 응용 (?) 이라 볼 수도 있을지도 모르겠다.

 

 

풀이 방법

 

한마디로 요약하면 앞에서부터 돌면서 자신의 값을 제외한 값을 곱하는 Prefix 

뒤에서부터 돌면서 자신의 값을 제외한 값을 곱하는 Postfix 를 이용한다.

 

실제 구현은 이 말과는 조금 다르지만 대충 이렇게 생각하면 이해가 편한 것 같다.

 

prefix를 1부터 시작해서 예제인 [1, 2, 3, 4]에 이 알고리즘을 돌리면 

result = [1, 1, 2, 6] 이 된다. 

 

이제부터는 뒤에서 루프를 돌린다.

 

예제의 답이 [24, 12, 8, 6]인걸 생각할 때

 

문제:   [1, 2, 3, 4]

result: [1, 1, 2, 6]

답:      [24, 12, 8, 6]

 

밑줄이 쳐진 4와 2를 곱하면 답인 8이 된다.

이 4라는 값을 postfix라는 정수에 기억하고

 

문제:   [1, 2, 3, 4]    postfix = 4

result: [1, 1, 8, 6]

답:      [24, 12, 8, 6]

 

3과 곱하면 답인 12가 나온다. postfix에 이 3이란 값을 다시 곱한다.

 

문제:   [1, 2, 3, 4]    postfix = 12

result: [1, 1, 8, 6]

답:      [24, 12, 8, 6]

 

postfix의 12와 밑줄이 쳐진 2를 곱하면 24가 된다.

 

이를 구현하면

 

 

풀이

 

사실 이 풀이를 한 유튜브의 댓글을 보면

 

아마존에서도 이 질문을 받았었다는 사람이 2명이나 된다. 

 

근데 그중 한 사람은 브루트포스로 풀고 통과했다 한다 ㅋㅋㅋ

 

사실 나누기를 쓸 수 있다면 O(n)으로 매우 쉽게 풀리는 문제인데

 

어째서인지 이 알고리즘은 다시 봐도 머리에 들어오지 않았어서 싫어하는 문제다

 

앞에서부터 돌면서 자신의 값을 제외한 값을 곱하는 Prefix

뒤에서부터 돌면서 자신의 값을 제외한 값을 곱하는 Postfix

 

이 것을 result라는 한 배열에서 하지 않고 prefix, postfix 라는 배열에 따로 담아서

 

result배열에다 곱을 계산하면 디버깅이 훨씬 편하다.

 

이런 식으로 이런 게 있구나라고나 알고만 있으면 다음에 또 사용하게 되는 일이 있을 것 같다.