Pramp - Array of Array Products

다섯번째 Pramp mock interview.

문제

배열이 주어진다. 자기자신을 제외한 나머지 배열을 모두 곱한 값으로 변환해라. (단, 나눗셈을 사용할 수 없다)

input:  arr = [8, 10, 2]
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10]

input:  arr = [2, 7, 3, 4]
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]

Leetcode 에서 이 문제와 동일: Leetcode - 238. Product of Array Except Self

후기

• brute force -> O(n^2)
• O(n)
  • all = multiply all
  • for -> arr[i] = all / arr[i];

여기까지는 풀어본 문제라서 쉽게 해결책을 떠올릴 수 있었다. 그런데 나눗셈을 사용했으므로 안됨. 다른 해결책을 사용해야하는데 잘 떠올리지 못함. 힌트를 two pass 로 풀어보라고 받았는데, 그래도 해결책을 잘 떠올리지 못했다. (각각의 값을 곱한것까지는 함. 그 이상 못함). 해결 아이디어를 더 받아서 꾸역꾸역 풀긴했는데 배열인덱싱이 복잡해서 완벽하게 풀지 못함. (그리고 벡터에서 런타임 에러가 발생).

이런 배열 인덱싱 문제는 반드시 [인덱스] 별로 직접 써보면서 따라가자. 머리로만 풀면 절대 안됨.

하지만 긍정적인 부분은 긴장을 전보다 훨씬 덜 했다는것. 막힐때 잘안풀릴때 더 초초하고 긴장하기 마련인데 이번엔 거의 긴장을 안했다. 계속 물어보고 생각을 계속 이야기했다. -> 많이 좋아진 부분!.

이거 못푼다고 내 인생이 망하는것도 아니고 걍 즐기자 ㅋㅋ

해결 아이디어

배열의 크기가 총 4일때, 최종 정답은 아래와같은 인덱스의 곱이 된다.

res[]   [1]*[2]*[3]   [0]*[2]*[3]   [0]*[1]*[3]   [0]*[1]*[2]

1부터 시작해 인덱스를 왼쪽에서 오른쪽으로 하나씩 곱하고, 그뒤에 맨마지막부터 1부터 시작해 오른쪽에서 왼쪽으로 하나씩 곱하면 아래와 같은 형태가 된다.

l->r:   1             1*[0]         1*[0]*[1]     1*[0]*[1]*[2]
l<-r:   *[3]*[2]*[1]  *[3]*[2]      *[3]          1

그리고 위 아래를 곱하면 res[] 답이된다!

예를 들어 아래와 같이 입력이 주어지면

arr = [2 7 3 4]

첫번째로 left -> right 로 하나씩 곱한다. 주의할 점은 리턴배열 res[]에 맨처음에는 1을 저장하고, 그뒤 [0] 부터 [2] 까지만 곱하는것. 그럼 [3] 인덱스 값이 arr[0] * arr[1] * arr[2] 곱한 값이 된다. 그러면 res[] 마지막 인덱스의 답(42)은 계산이 완료된 상태

res = [7*3*4  2*3*4  2*7*4  2*7*3]
      [1      1*2    1*2*7  1*2*7*3]  

이제 right -> left순으로 계산한다.

res = [7*3*4   2*3*4   2*7*4   2*7*3]
      [1       1*2     1*2*7   1*2*7*3]  (left -> right)
      1*7*3*4  1*3*4   1*4     1         (right -> left)

최종 아래와 같이 정답이 계산된다. 어렵지만 기발한 아이디어 ㅇㅈ..

res = [7*3*2 2*3*4 2*7*4 2*7*3]

대략 이렇게 곱하는 구조.

       _____     l->r
arr = [2 7 3 4]
         ^^^^^   l<-r

더 자세히 살펴보니 이런 구조가 보인다..!

    _____  l->r
[2] 7 3 4

      ___  l->r
2 [7] 3 4
^          l<-r

        _  l->r
2 7 [3] 4
^^^        l<-r

2 7 3 [4]
^^^^^      l<-r

이 방식으로도 해결할 수 있을듯.

해결

#include <iostream>
#include <vector>

vector<long> arrayOfArrayProducts(const vector<int>& arr) 
{
  vector<long> res;
  if (arr.size() <= 1)
    return res; // return empty vector
  res = vector<long>(arr.size(), 0);
  
  int temp = 1;
  for (int i = 0; i < arr.size(); i++) {
    res[i] = temp;
    temp *= arr[i];
  }
  temp = 1;
  for (int i = arr.size() - 1; i >= 0; i--) {
    res[i] *= temp;
    temp *= arr[i];
  }
  return res;
}

int main() {
  return 0;
}