티스토리 뷰

https://programmers.co.kr/learn/courses/30/lessons/43165?language=swift 

 

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

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수

programmers.co.kr

https://sio2whocode.tistory.com/171

 

[프로그래머스] 타겟 넘버 (C++)

https://programmers.co.kr/learn/courses/30/lessons/43165?language=cpp 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를..

sio2whocode.tistory.com

풀이는 C++ 풀이와 같다.

 

Swift로 풀이하는 과정에서 알게 된 점은

암시적 추출 옵셔널로 선언하는 것이 자원 소모가 크다는 점이다.

시간이 그러지 않았을 때보다 4배정도 더 측정됐다.

 

1. numbers배열 전역변수를 암시적 추출 옵셔널로 선언했을 때 : 약 400ms

2. numbers배열 전역변수를 일반 [Int] 타입으로 선언했을 때 : 약 100ms

3. numbers배열을 dfs함수의 매개변수로 전달할 때 : 약 30ms

 

1번

import Foundation

var globalNumbers: [Int]!
var globalTarget: Int!
var count: Int = 0

func dfs(_ sum: Int, _ i: Int){
    if i == globalNumbers.count - 1 {
        if sum == globalTarget {
            count += 1
        }
        return
    }

    dfs(sum + globalNumbers[i+1], i+1);
    dfs(sum - globalNumbers[i+1], i+1);
}

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

    dfs(globalNumbers[0], 0)
    dfs(-globalNumbers[0], 0)

    return count
}

2번

import Foundation

var globalNumbers: [Int] = []
var globalTarget: Int = 0
var count: Int = 0

func dfs(_ sum: Int, _ i: Int){
    if i == globalNumbers.count - 1 {
        if sum == globalTarget {
            count += 1
        }
        return
    }

    dfs(sum + globalNumbers[i+1], i+1);
    dfs(sum - globalNumbers[i+1], i+1);
}

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

    dfs(globalNumbers[0], 0)
    dfs(-globalNumbers[0], 0)

    return count
}

3번

import Foundation

var count: Int = 0

func dfs(_ numbers: [Int], _ target: Int, _ sum: Int, _ i: Int){
    if i == numbers.count - 1 {
        if sum == target {
            count += 1
        }
        return
    }
    
    dfs(numbers, target, sum + numbers[i+1], i+1);
    dfs(numbers, target, sum - numbers[i+1], i+1);
}

func solution(_ numbers:[Int], _ target:Int) -> Int {
    dfs(numbers, target, numbers[0], 0)
    dfs(numbers, target, -numbers[0], 0)
    
    return count
}
댓글
댓글쓰기 폼