04/17 알고리즘 공부(94) - 타겟 넘버

조건

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

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한조건

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	terget	return
[1, 1, 1, 1, 1]	3	5

알고리즘 예상

1. dfs를 이용해 푸는 문제 같아서 일단 93번 문제를 풀기 전에 풀어보기로 했다.
2. boolean 값을 이용해 true면 더하기를, false면 빼기를 진행하는 방법을 이용해 보기로 했다.

 

초기 코드

class Solution {
    fun solution(numbers: IntArray, target: Int): Int {
        var answer = 0
        return answer
    }
}

 

내 코드

class Solution {
    var answer = 0
    lateinit var number: IntArray
    lateinit var visit: BooleanArray
    fun solution(numbers: IntArray, target: Int): Int {
        number = numbers
        visit = BooleanArray(numbers.size) { true }
        for (i in number.indices) {
            dfs(i, target)
        }
        println(answer)
        return answer
    }

    fun dfs(now: Int, target: Int) {
        visit[now] = false

        for (i in now..number.lastIndex) {
            if (visit[i]) {
                dfs(i, target)
            }
        }

        if (now + 1 == number.size) {
            checkResult(target)
        }

        visit[now] = true

        if (now + 1 == number.size) {
            checkResult(target)
        }
    }

    fun checkResult(target: Int) {
        var result = 0
        for (i in number.indices) {
            if (visit[i]) result += number[i]
            else result -= number[i]
        }
        if (result == target) answer++
    }
}

많이 많이 헤매고 억지로 풀었다. 해당 로직에 익숙해질 필요가 있어보인다.

다른 사람의 풀이

class Solution {
    fun solution(numbers: IntArray, target: Int): Int {
    return numbers.fold(listOf(0)) { list, i ->
        list.run {
            map { it + i } + map { it - i }
        }
    }.count { it == target }
}
}

class Solution {
    fun solution(numbers: IntArray, target: Int): Int {
        var answer = 0
        fun dfs(sum: Int,idx: Int){
            if(idx<numbers.size-1){
                dfs(sum+numbers[idx],idx+1)
                dfs(sum-numbers[idx],idx+1)
            }
            else{
                if(sum+numbers[idx] == target) {answer++}
                if(sum-numbers[idx] == target) {answer++}
            }
        }
        dfs(0,0)
        return answer
    }
}

개선점 또는 배운점

1. 위 풀이는 fold를 이용해 list의 길이를 2배씩 늘려가면서 연산을 처리했다.
2. 아래 풀이는 t/f 없이 단순히 두 가지의 연산을 모두 실행하는 방향으로계산을 진행했다.