[LeetCode] 605. Can Place Flowers

[LeetCode] 605. Can Place Flowers

 

 

- DP 활용해 누적곱으로도 풀어낼 수 있는데, 특정 조건이 만족하면 그대로 종료할 수 있는 로직을 통해 특정 데이터 조건에서 시간 복잡도 개선이 불가하여, 다른아이디어 적용

 

 

문제 링크

https://leetcode.com/problems/can-place-flowers/?envType=study-plan-v2&envId=leetcode-75

 

리트코드

 

문제풀이

아이디어, 나 자신을 제외한 모든 수를 곱하는 거라서, 이미 모든 수를 다 곱해놓고, 출력 전에 나 자신으로 나누기

이 과정에서 특정 조건을 만족한 경우 엣지케이스를 통한 처리로 시간 복잡도 줄임

 

분석 및 주의점

• 0이 2개 이상이면 모든 자리는 0이므로 전체 곱을 수행하는 도중에 0이 2개 이상이라면 그대로 종료
• 0이 1개라면 나를 제외한 모든 자리는 0임
• 0이 0개라면 전체를 나로 나누면 된다.
• 나눌때 0 으로 나누면 크래시 발생하므로 이것만 주의해서 개발하면 끝
• 시간 복잡도 개선을 위해 total을 구하는 도중이라도 zeroCount가 2가 넘으면 그대로 종료

 

class Solution {
    func productExceptSelf(_ nums: [Int]) -> [Int] {
         var nums = nums
        
        var zeroCount = 0
        var total = 1
        
        var num = 0
        for i in nums.indices {
            num = nums[i]
            if num == 0 {
                zeroCount += 1
                total *= 1
                
                if zeroCount >= 2 {
                    nums = nums.map { num in
                        return 0
                    }
                    return nums
                }
            } else {
                total *= num
            }
        }
        
        if zeroCount >= 2 {
            nums = nums.map { num in
                return 0
            }
            return nums
        } else if zeroCount == 1 {
            nums = nums.map { num in
                if num == 0 { return total }
                else { return 0 }
            }
        } else {
            nums = nums.map { num in
                if num == 0 { return total }
                else { return total / num }
            }
        }
        
        return nums
    }
}