[LeetCode]238.자신을 제외한 배열의 곱

[문제]

배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라

(나눗셈은 사용하지 않는다)

 

·입력

[1,2,3,4]

 

·출력

[24,12,8,6]

 

 

나눗셈을 사용할 수 없기 떄문에 자기 자신을 제외하고 왼쪽의 곱셈 결과와 오른쪽의 곱셈 결과를 곱해야 한다.

 

먼저 자기 자신을 기준으로 왼쪽 곱셈의 결과를 구현해보자.

위 그림과 같이 1일땐 왼쪽 곱셈 결과가 1, 2일때 1, 3일때 2, 4일때 6이 된다.

 

nums=[1,2,3,4]

out=[]
p=1

#왼쪽 곱셈
for i in range(0,len(nums)):
  out.append(p)
  p=p*nums[i]

print(out)

· 출력

[1, 1, 2, 6]

 

다음은 오른쪽이다.

1일땐 오른쪽 곱셈 결과가 24, 2일때 12, 3일때 8, 4일때 1이 된다.

위 코드에서 out처럼 결과 값을 별도의 리스트를 만들어 저장하면 공간 복잡도가 높아지기 때문에 위에서 만든 out을 그대로 사용한다. 

p=1

#왼쪽 곱셈 결과에 오른쪽 값을 차례대호 곱셈
for i in range(len(nums)-1,-1,-1):
  out[i]=out[i]*p
  p=p*nums[i]
return out

range의 인수를 3개 사용하면 range(시작,끝,증분)이 된다.

 

 

·최종코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        out=[]
        p=1
        
        #왼쪽 곱셈
        for i in range(0,len(nums)):
            out.append(p)
            p=p*nums[i]
            
        p=1
       
       #왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
        for i in range(len(nums)-1,-1,-1):
            out[i]=out[i]*p
            p=p*nums[i]
            
        return out