[LeetCode]Medium - 238. Product of Array Except Self

Medium - 238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/

 

문제 해석

반복문을 한번만 돌려 나를 제외한 모든 값들의 곱을 구해야 한다.

대신! 나누기 연산을 사용하지 않을 것!

---

풀이 방법

풀이 접근 과정

인터넷 힌트 참고함.

자신을 기준으로 왼쪽값들의 곱을 구하고

자신을 기준으로 오른쪽값들의 곱을 구해

그 곱을 다시 곱하면 된다.

 

최종 소스코드

class Solution {
    fun productExceptSelf(nums: IntArray): IntArray {
        val answer = IntArray(nums.size) { 1 }

        for (i in 1 until nums.size) {
            answer[i] = (answer[i-1] * nums[i-1])
        }

        var prod = 1
        for (i in nums.size-2 downTo 0) {
            answer[i] *= (prod * nums[i+1])
            prod *= nums[i+1]
        }

        return answer
    }
}

1. 정답을 리턴할 배열 answer를 선언해준다. (정답 배열은 공간복잡도에 영향을 주지 않음.)
2. 우선 나를 기준으로 왼쪽의 값들을 곱해주어 answer에 저장한다.
3. 반대로 오른쪽을 돌 때는 prod 변수를 이용하여 오른쪽 곱의 누적값을 저장시켜야 한다. (공간복잡도: O(1))
4. answer에 prod 값과 나의 바로 오른쪽 값을 곱하고 왼쪽의 누적값을 곱하면 정답이 된다.

	1	2	3	4
왼쪽으로 이동		1	1*2	1*2*3
오른쪽으로 이동	2*3*4	3*4	4
변수값	answer = 1 prod = 2*3*4	answer = 1 prod = 3*4	answer = 2 prod = 4	answer = 6 prod=1
결과값	1*2*3*4 = 24	1*3*4 = 12	2*1*4 = 8	6*1 = 6

---

Comment

문제 제한 조건 때문에 접근하기가 까다로웠던 문제였다...

아무리 생각해봐도 이중 for문 외의 접근 방법은 떠오르지 않았다.

결국... 인터넷 힌트 참고 ㅠㅠ

(그래도 소스코드는 보지 않음!! ㅎㅎ.....)

 

인터넷을 통해 풀이를 참고하긴 했지만 그래도 풀었다는 사실에 의의를 둔다 !!