[Leetcode/Medium] 자신을 제외한 배열의 곱 (238. Product of Array Except Self, Swift)

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

 

🤔 문제 설명

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

숫자의 접두사 또는 접미사의 곱은 32비트 정수에 들어맞는 것을 보장합니다. 단, 나눗셈을 사용하지 않고 O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

nums = [1,2,3,4]
// [24, 12, 8, 6]

 

💡 풀이

문제 가장 마지막줄에 나눗셈을 사용할 수 없다는 조건 때문에, 전체 곱을 구해두고 각 요소별로 자기 자신을 나누는 방법은 사용할 수가 없다. 그래서 결국은 누적 곱셈을 이용하는 풀이 방법을 생각했다.

1. 우선 입력 리스트 nums 길이에 맞는 result 리스트를 1로 초기화해준다. (예제 기준: [1, 1, 1, 1])
2. 좌에서 우 순서로 첫 항을 놔두고 끝에서 2번째 지점까지 누적 곱을 구한다. (예제 기준: [1, 1, 2, 6])
3. 우에서 좌 순서로 첫 항을 놔두고 처음 2번째 지점까지 다시 뒤에서부터 누적 곱을 구한다. (예제 기준: [24, 12, 8, 6])

결국 가장 핵심은 결과 리스트를 채울 때는 첫 한 칸을 띄고 누적곱을 추가한다는 것과, nums 누적곱은 마지막 한 개를 하지 않는다는 것이다. 

즉, 리스트의 인덱스를 잡는 범위를 정확하게 잡아주는 것이 코드를 짤 때의 포인트라고 생각하면 되겠다.

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 152ms (Beats 83.10%), Memory : 24.91MB (Beats 74.76%)

class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        var numsResult = [Int](repeating: 1, count: nums.count)
        var accLeft = 1
        var accRight = 1

        for (index, num) in nums.enumerated() {
            if (index == nums.count-1) { break }
            accLeft *= num
            numsResult[index+1] *= accLeft
        }

        for (index, num) in nums.reversed().enumerated() {
            if (index == nums.count-1) { break }
            accRight *= num
            numsResult[nums.count-index-2] *= accRight
        }

        return numsResult
    }
}