Funcia
Lv.1arraymathprefix-sum

나를 뺀 나머지의 곱

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 nums가 주어집니다. 각 위치 i마다 nums[i]를 제외한 나머지 모든 원소의 곱을 구해, 같은 순서로 담은 배열을 반환하세요.

곱은 매우 커질 수 있으므로 각 값을 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지로 반환합니다. nums에는 0이 들어 있을 수도 있습니다.

입출력 예

numsresult
[1, 2, 3, 4][24, 12, 8, 6]
[3, 0, 5][0, 15, 0]
[1000000000, 1000000000][1000000000, 1000000000]

입출력 예 설명

예 1 — 0번 위치는 2×3×4 = 24, 1번 위치는 1×3×4 = 12, 2번 위치는 1×2×4 = 8, 3번 위치는 1×2×3 = 6입니다.

예 2 — 0을 빼고 곱하는 위치는 1번뿐이라 3×5 = 15이고, 나머지 위치의 곱에는 0이 들어 있습니다.

예 3 — 각 위치에서 곱하는 원소는 하나뿐이므로 그 값 자체가 답입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[]) → int[]

제한 사항

  • 2≤2 \le nums.length ≤200,000\le 200{,}000
  • 0≤0 \le nums[i] ≤109\le 10^9
  • 반환하는 각 값은 1,000,000,0071{,}000{,}000{,}007로 나눈 나머지입니다.

기대 복잡도

시간
O(N)
공간
O(N)

입출력 예

nums기대 출력
[1,2,3,4][24,12,8,6]
[3,0,5][0,15,0]
[1000000000,1000000000][1000000000,1000000000]

힌트

힌트

i를 뺀 곱은 i보다 왼쪽 원소들의 곱 × i보다 오른쪽 원소들의 곱입니다.

  • left[i] = nums[0] × … × nums[i-1] (왼쪽에서 한 번 훑으며 누적)
  • right[i] = nums[i+1] × … × nums[n-1] (오른쪽에서 한 번 훑으며 누적)

답은 left[i] × right[i]이고, 곱할 때마다 나머지를 취하면 됩니다. 두 값의 곱은 32비트 정수를 넘으므로 64비트로 계산하세요.

전체 곱을 구한 뒤 nums[i]로 나누는 방법은 0이 있으면 쓸 수 없고, 나머지 연산 아래에서는 평범한 나눗셈도 성립하지 않습니다.

복잡도 목표

위치마다 나머지 원소를 모두 곱하면 O(N2)O(N^2)로 시간 초과입니다. 누적 곱 두 번으로 O(N)O(N)에 풀 수 있습니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251356 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.