[LeetCode] 238. Product of Array Except Self

문제

leetcode.com/problems/product-of-array-except-self/

Product of Array Except Self - LeetCode

 

잠깐

array에서 자기 자신을 제외한 곱의 값을 넘겨 주는 문제.

 

 

코드

class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
        var answer: [Int] = Array(repeating: 0, count: nums.count)
        var allProductResultExceptZero = 1
        var zeroCount = 0
    
        nums.forEach { num in
            if num == 0 {
                zeroCount += 1
            } else {
                allProductResultExceptZero *= num
            }
        }
    
        if zeroCount > 1 {
            allProductResultExceptZero = 0
        }
    
        for index in 0..<nums.count {
            if zeroCount == 0 {
                answer[index] = allProductResultExceptZero / nums[index]
            } else if zeroCount == 1,
                    nums[index] == 0 {
                answer[index] = allProductResultExceptZero
            }
        }
        return answer
    }
}

 

설명

이중포문을 사용하면 될 것 같지만, 시간 초과가 발생할것 같기도 하고, 그러네요.

그리고 문제 조건을 보면 -30 ~ 30으로 제한돼있는데, 여기서 뭔가 길이 보였습니다.

(여러분 코딩테스트에선, 제한 조건을 통해 힌트를 발견할 줄 알아야 합니다)

 

0을 제외한 모든 수를 곱한 결과값을 계산해놓고, 엘리먼트 수에 따라 계산하면 되겠어요.

포인트는 배열 속 zero의 개수입니다.

 

zero가 0개인 케이스 :

-> 모든 수를 곱한 결과값 / 엘리먼트 자기 자신 

 

zero가 1개인 케이스 : 

-> 엘리먼트 자신이 0인 경우 : 모든 수를 곱한 결과값

-> 엘리먼트 자신이 0이 아닌 경우 : 0

 

zero가 2개 이상인 케이스 :

-> 자신이 0이더라도, 0인 다른 엘리먼트가 존재하기 때문에, 항상 0이 나옵니다.

 

회고

사실 처음엔 다음과 같이 구현 했습니다.

class Solution {     func productExceptSelf(_ nums: [Int]) -> [Int] {         var zeroCount = 0         var isHasNum = false         var multipleValueExcluseZero = 1                  for num in nums {             if num == 0 {                 zeroCount += 1             } else {                 isHasNum = true                 multipleValueExcluseZero *= num             }         }                  if !isHasNum {             multipleValueExcluseZero = 0         }                   var result: [Int] = []          for num in nums {             if num == 0 {                 if zeroCount == 1 {                     result.append(multipleValueExcluseZero)                 } else {                     result.append(0)                 }             } else {                 if zeroCount > 0 {                     result.append(0)                  } else {                     result.append(multipleValueExcluseZero/num)                  }             }         }                  return result     } }

비어있는 result array를 선언하고 append를 통해 값들을 추가했는데, 아무래도 배열 자료구조는 insert, delete에 비효율적이기 때문에,

사이즈를 지정한 array를 선언하도록 수정했습니다.

사이즈 지정 어레이 선언 방법은 다음과 같아요. 

var result: [Int] = [Int](repeating: 0, count: nums.count)

 

developer.apple.com/documentation/swift/array/1641692-init

Apple Developer Documentation

 

append를 회피한 이유는 다음과 같아요.

평균적으로 빅오(1)이지만, 재할당으로 메모리를 늘려야할 경우 빅오(n)네요.

 

그리고 실제적으로 수행 결과, array 사이즈 지정 선언 방식이 근소하지만 더 효율적 결과가 나왔어요.

 

append 사용 방식은 212ms, 21.9MB

사이즈 지정 방식은 204ms, 20.7MB 

 

생각해보니, 사용 메모리를 21.9MB에서 20.7MB로, 런타임 속도를 212ms에서 204ms로 줄였으니, 꽤 괜찮은 최적화인가요?

참고로, 속도와 메모리는 사이트 환경에 따라 다릅니다. 같은 코드여도 결과가 달라요.