swift 리트코드 문제풀이 - leetcode 238 자신을 제외한 배열의 곱

swift 리트코드 문제풀이 - leetcode 238 자신을 제외한 배열의 곱

 

leetcode 238. Product of Array Except Self

 

문제

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

 

예제

Input: nums = [1,2,3,4]

Output: [24,12,8,6]

 

예제

Input: nums = [-1,1,0,-3,3]

Output: [0,0,9,0,0]

 

처음에 문제를 봤을때 쉽네? 라고 생각했다...ㅋㅋ

 

ㅋㅋㅋㅋㅋ

ㅋㅋㅋㅋ .........

.......

 

반복문과 스위프트의 reduce 함수를 이용해서 반복문에서 자신은 * 1을 하고 나머지 숫자는 reduce를 이용해서 전부 곱해버리는 로직을 생각했다. 아래처럼 간단하게 작성했는데 정답이 출력되더라.. 그래서 괜찮은 풀이인줄 알았다.

 

문제는 leetcode에 summit을 했을때 시간 초과가 나오는데 파라미터 nums 배열의 개수가 1만개 이상이 되면 처리 속도가 많이 느려진다...

그래서 다른 방법으로 접근해야 한다. 배열의 요소가 적으면 상관이 없는데 배열의 요소가 몇 만개 몇 십만개면 아래 처럼 작성하면 안된다.. 

 

func productExceptSelf(_ nums: [Int]) -> [Int] {

    var resultArray: Array<Int> = []

    //숫자하나한 돌면서
    for (idx , _) in nums.enumerated(){
        
        let resultNum = nums.enumerated().reduce(1) { accumulate, current in
            //자신의 숫자에는 * 1
            if idx == current.0 {
                return 1 * accumulate
            }else{
                return current.1 * accumulate
            }
        }
        resultArray.append(resultNum)
    }

    return resultArray
}

 

이중 for문을 쓰지말고 for문 하나로 해결해보자...

 

일단 아래 그림의 아웃풋을 보자. 인풋인 자신의 숫자를 빼고 나머지 숫자들을 곱하는 과정을 나타낸다.

인풋 1은 자신의 숫자 1을 제외한 나머지 2 와 3을 곱했다. 인풋 2는 자신을 제외한 숫자 1과 3을 곱한다. 마지막 3은 자신의 숫자 3을 제외한 1과 2를 곱한다.

 

먼저 for문으로 배열 왼쪽 부터 오른쪽 방향으로 하나씩 이동하면서 이전 index의 값과 이전 input 값을 곱한 값을 leftToright 배열에 넣어준다. 아래 예를 들면 인풋 1에는 이전 index의 값이 없으므로 1을 넣어주면된다. 아래 그림에는 빈칸이다.  그리고 인풋 2의 위치에는 leftToright 배열의 이전 index에 위치한 값과 배열의 이전 index 인풋값을 곱한 값을 넣어주면된다.

 

2의 leftToright 배열의 이전 index에 위치한 값 : 1

2의 인풋 배열의 이전 index에 위치한 값 : 1

그래서 인풋 2의 leftToRight 배열에는 1이 들어간다.

 

이제 인풋 3을 채워보자.

 

3의 leftToright 배열의 이전 index에 위치한 값 : 1

3의 인풋 배열의 이전 index에 위치한 값 : 2

그래서 인풋 3의 leftToRight 배열에는 1*2가 들어간다.

 

 

위의 그림처럼 rightToLeft 배열에도 마찬가지로 값을 넣어주고 두 배열의 동일한 위치에 있는 값을 곱해주면 된다.

 

var productExceptSelfArray = Array(repeating: 1, count: 10000)

func productExceptSelf2(_ nums: [Int]) -> [Int] {
    
    //결과 배열
    var resultArray = Array(repeating: 1, count: nums.count)
    
    //왼쪽 배열
    var leftToRight :[Int] = []
    
    //오른쪽 배열 - nums의 개수 크기의 배열 생성
    var rightToLeft = Array(repeating: 1, count: nums.count)
    
    //left->right로 이전 인덱스까지의 누적곱을 넣어줌
    for (idx, _) in nums.enumerated(){
        (idx == 0) ? leftToRight.append(1) : leftToRight.append(leftToRight[idx-1] * nums[idx-1])
    }
    
    //right->left로 이전 인덱스까지의 누적 곱 넣기
    var i = nums.count-1
    while i >= 0 {
        if(i == nums.count-1){
            rightToLeft[i] = 1
        }else{
            rightToLeft[i] = (rightToLeft[i+1] * nums[i+1])
        }
        
        // 두 배열의 요소 곱해서 결과 배열에 넣어주기
        resultArray[i] = (leftToRight[i] * rightToLeft[i])

        i -= 1
    }

    print(">>>> leftToRight :\( leftToRight )")
    print(">>>> rightToLeft :\( rightToLeft )")

    return resultArray
}
print(">>>> productExceptSelf2 :\( productExceptSelf2(productExceptSelfArray) )")

 

 

 

결과

 

너무힘들다.. 오늘은 여기까지..

 

 

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