Swift) 프로그래머스(Lv2) - 타겟 넘버 (BFS 와 Remove(:at)에 대한 고찰)

programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

안녕하세요 후르륵짭짭 입니다.

어렵지 않은 문제를 정말 긴 시간 동안 고생 했습니다.

계속 시간초과 가 발생했습니다....

DFS말고 BFS로 풀 수 있지 않을까 해서 BFS로 풀려고 했는데,,,

Swift로 풀려면 계속 시간 초과가 발생하는데,,, 그 이유를 못 찾아서 많이 고생 했습니다.

 

** 문제 해결 방법 **

위의 이미지 처럼 이진 트리 형태로 접근 했습니다

func solution2(_ numbers:[Int], _ target:Int) -> Int {

    var queue : [Int] = [0]
    var tempQueue : [Int] = []
    var answer = 0

    for index in 0...numbers.count {
        
        var plusPoint = 0
        
        if index != numbers.count {
            plusPoint = numbers[index]
        }
        
        if index == numbers.count {
            
            answer = queue.filter { (element) -> Bool in
                return element == target ? true : false
            }.count
        
            break
        }
        
        while !queue.isEmpty {
            
            let item = queue.first!
            queue.removeFirst()
            
            tempQueue.append(item + plusPoint)
            tempQueue.append(item - plusPoint)
            
        }
        
        queue = tempQueue
        tempQueue = []
        
    }
    
    return answer
    
}

접근 방법은 정말 단순하고 어렵지 않습니다.

numbers 안에는 숫자들이 들어가 있고 그 숫자들을 더하고 빼거나 해서 목표하는 숫자를 만드는 겁니다.

따라서 방법은 빼냐 더하냐 문제 입니다. 그래서 이진 트리로 접근 했습니다.

그리고 트리의 깊이는 2^20 승 까지 내려가니,,, 1024 * 1024로 100만 정도 라서 1초를 넘어가지 않을 겁니다.

하지만,,,,,, 저 코드를 제출하면 

이렇게 됩니다....

정말 다양한 코드를 짜보고,,,,,

(제약 조건을 걸어 준 BFS 코드)

func solution(_ numbers:[Int], _ target:Int) -> Int {

    var queue : [Int] = [0]

    var answer : Int = 0

    var total = numbers.reduce(0, +)

    for index in 0...numbers.count {

        var tempQueue : [Int] = []
        var plusPoint : Int = 0

        if index != numbers.count {
            plusPoint = numbers[index]
        }

//        print("새로운 시작 : \(plusPoint)")

        while !queue.isEmpty {

            let item = queue.first!
//            print(item)
            queue.removeFirst()

            if item == target && index == numbers.count {
                answer += 1
            }

            if item + total >= target {

                if item - total < target{
                    tempQueue.append(item + plusPoint)
                }

                tempQueue.append(item - plusPoint)
            }

        }

        total -= plusPoint
        queue = tempQueue

    }

    return answer
}

이렇게,,, 해줘도 계속 시간 초과가 발생하게 됩니다...

 

이렇게 해결 하지 못한 이유는 바로 배열의 remove 때문 입니다..... 😭😭😭😭😭😭😭😭😭😭

이거 때문에 4시간 정도 사용한 거 같습니다...

developer.apple.com/documentation/swift/array/1641390-remove

Apple Developer Documentation

Complexity: O(n), where n is the length of the array.

시간 복잡도가 O(n) 입니다. 따라서 Queue에 들어 있는 양이 백만 이라고 한다면 remove 할 때 , 또 백만을 돌게 됩니다...

따라서,,,, 시간 초과가 발생한 겁니다....

따라서 위의 코드들을 remove를 사용하지 않고 수정해줄 필요가 있습니다.

func solution(_ numbers:[Int], _ target:Int) -> Int {

    var queue : [Int] = [0]
    var tempQueue : [Int] = []
    var answer = 0

    for index in 0...numbers.count {
        
        var plusPoint = 0
        
        if index != numbers.count {
            plusPoint = numbers[index]
        }
        
        if index == numbers.count {
            
            answer = queue.filter { (element) -> Bool in
                return element == target ? true : false
            }.count
        
            break
        }
        
        var cnt = 0
        
        while cnt < queue.count {
            
            let item = queue[cnt]
            
            tempQueue.append(item + plusPoint)
            tempQueue.append(item - plusPoint)
            
            cnt += 1
        }
        
        queue = tempQueue
        tempQueue = []
        
    }
    
    return answer
    
}

따라서 이렇게 cnt라는 새로운 변수를 생성해서 해결해줘야 합니다......

이러면 쉽게 문제를 통과 할 수 있습니다.

(제한 조건을 걸어준 해결 코드)

func solution(_ numbers:[Int], _ target:Int) -> Int {

    var queue : [Int] = [0]

    var answer : Int = 0

    var total = numbers.reduce(0, +)

    for index in 0...numbers.count {

        var tempQueue : [Int] = []
        var plusPoint : Int = 0

        if index != numbers.count {
            plusPoint = numbers[index]
        }

    var cnt = 0

        while cnt < queue.count {

            let item = queue[cnt]
            

            if item == target && index == numbers.count {
                answer += 1
            }

            if item + total >= target {

                if item - total < target{
                    tempQueue.append(item + plusPoint)
                }

                tempQueue.append(item - plusPoint)
            }
            
            cnt += 1

        }

        total -= plusPoint
        queue = tempQueue

    }

    return answer
}

 

결국, Swift에서 queue를 사용할 때는 remove를 사용해서 탐색하는 것이 아니라

새로운 변수를 생성해서 위에 처럼 cnt로 접근 하던가

아니면 아래 처럼 for문을 사용해서 접근 할 필요가 있습니다.

func solution3(_ numbers:[Int], _ target:Int) -> Int {

    var queue : [Int] = [0]
    var tempQueue : [Int] = []
    var answer = 0

    for index in 0...numbers.count {
        
        var plusPoint = 0
        
        if index != numbers.count {
            plusPoint = numbers[index]
        }
        
        if index == numbers.count {
            
            answer = queue.filter { (element) -> Bool in
                return element == target ? true : false
            }.count
        
            break
        }
        
        for element in queue{
            
            tempQueue.append(element + plusPoint)
            tempQueue.append(element - plusPoint)
            
        }
        
        queue = tempQueue
        tempQueue = []
        
    }
    
    return answer
    
}