238. Product of Array Except Self

LeetCode 238번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Product of Array Except Self - LeetCode

풀이

아이디어

나눗셈을 사용하지 못하기 때문에 전체 곱을 구해서 nums[i] 원소를 나눈 값을 answer[i]에 넣어 주는 방법을 생각했다가 바로 포기했다.

그림을 그려 보니 nums[i] 를 기준으로 왼쪽 구간과 오른쪽 구간이 1칸씩 늘어나고, 1칸씩 줄어드는 모양이라서 왼쪽 부분 (prefix)는 계속 구간을 늘려주고, 오른쪽 부분(suffix)는 계속 구간을 줄여주는 방식으로 문제를 풀었다.

코드

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array<number>(nums.length);

  // answer 배열에 prefix값 설정해주기
  let prefix = 1;
  for (let idx = 0; idx < n; idx++) {
    answer[idx] = prefix;
    prefix *= nums[idx];
  }

  // 각 prefix에 suffix 값 누적해서 곱해주기
  let suffix = 1;
  for (let idx = n - 1; idx >= 0; idx--) {
    answer[idx] *= suffix;
    suffix *= nums[idx];
  }

  return answer;
}

시간 / 공간 복잡도

• 시간 복잡도: prefix를 구하는 과정에서 O(n) + suffix를 구하는 과정에서 O(n) 이므로 O(n)
• 공간 복잡도: answer 배열을 제외한 추가적인 공간을 사용하지 않으므로 O(1)