알고리즘 문제풀이 정리 - Arrays & Hashing (3)
이전 게시글에서 이어서 작성되는 3부이다.
Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].
Each product is guaranteed to fit in a 32-bit integer.
Follow-up: Could you solve it in O(n)O(n) time without using the division operation?
Example 1:
Input: nums = [1,2,4,6]
Output: [48,24,12,8]Example 2:
Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]Constraints:
2 <= nums.length <= 1000-20 <= nums[i] <= 20
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
product=1
cnt=0
zerospot=-1
for i, num in enumerate(nums):
if num==0:
cnt+=1
zerospot=i
else:
product*=num
answer=[0]*len(nums)
if cnt>1:
return answer
elif cnt==1:
answer[zerospot]=product
return answer
for i in range(len(nums)):
product/=nums[i]
answer[i]=int(product)
product*=nums[i]
return answer처음 숫자들을 탐색할 때 모두 곱하면서 0위치와 개수를 마킹하고 0대신 1을 곱한다음
그 다음 탐색할 때 역산한다. 라는 개념으로 접근했다.
그러다 문득 0이 1개일 때와 2개이상일 때의 예외 케이스만 잘 다루며 되지 않나 싶어서 그 부분에 초점을 맞추어 코드를 짰다.
0이 2개 이상인 경우에는 nums[i]를 제외하고 곱한 값이 i와 상관없이 모두 0이 된다.
0이 1개인 경우에는 nums[i]가 0이 아닐 때 모두 0이 된다. nums[i]==0 일 때 0을 제외한 값들의 곱만 output[i]에 넣어주면 된다.
0이 없는 경우에는 0의 개수를 세면서 미리 계산해놓은 전체곱에서 nums[i]를 나눈 값을 기록한다.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
for i in range(n):
prod = 1
for j in range(n):
if i == j:
continue
prod *= nums[j]
res[i] = prod
return res각 output[i]에 대해 nums[i]를 제외한 모든 nums를 매번 각각 곱하는 방식으로 해결했다.
시간 복잡도는 이다.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
prod, zero_cnt = 1, 0
for num in nums:
if num:
prod *= num
else:
zero_cnt += 1
if zero_cnt > 1: return [0] * len(nums)
res = [0] * len(nums)
for i, c in enumerate(nums):
if zero_cnt: res[i] = 0 if c else prod
else: res[i] = prod // c
return res내가 한 풀이와 같다.
시간복잡도는 .
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
pref = [0] * n
suff = [0] * n
pref[0] = suff[n - 1] = 1
for i in range(1, n):
pref[i] = nums[i - 1] * pref[i - 1]
for i in range(n - 2, -1, -1):
suff[i] = nums[i + 1] * suff[i + 1]
for i in range(n):
res[i] = pref[i] * suff[i]
return resprefix : 접두사 / suffix : 접미사
앞에서부터 연속해서 곱한 값들을 저장해놓은 배열 하나, 뒤에서부터 연속해서 곱한 값들을 저장해놓은 배열 하나를 각각 만들고 그 둘의 조합으로 output 배열을 만드는 방식이다. 이 방법을 이용하면 division을 쓰지 않아도 된다.
시간복잡도는 .
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * (len(nums))
prefix = 1
for i in range(len(nums)):
res[i] = prefix
prefix *= nums[i]
postfix = 1
for i in range(len(nums) - 1, -1, -1):
res[i] *= postfix
postfix *= nums[i]
return res어차피 output 배열에 prefix와 suffix의 값을 곱하여 저장할 것이라면, 처음부터 output 배열인 res에 저장하면 되지 않겠냐는 발상이다. 그래서 prefix와 suffix에 대해 각각 n개의 배열을 만드는 대신 prefix, postfix라는 변수 하나만 선언하여 앞의 방식보다 공간 복잡도를 더 줄여 최적화 했다.
뒤에 문제들 중 Valid Sudoku 문제를 풀지 못했는데 해당 문제를 풀고 리뷰하고 싶어서 Arrays & Hashing 게시글 마무리를 한 번 더 미루게 되었다. 다음시간에 Array & Hashing 정리 마무리할 예정이다.