10. 타겟 넘버

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

파이썬

def solution(numbers, target):
    answer = 0
    for checker in range((1 << len(numbers)) - 1, -1, -1):
        total = 0
        for i in range(len(numbers) - 1, -1, -1):
            divisor = 1 << i
            if checker // divisor == 1:
                total += numbers[len(numbers) - i - 1]
            else:
                total -= numbers[len(numbers) - i - 1]
            checker %= divisor
        if total == target:
            answer += 1
    return answer
    
'''
테스트 1 〉	통과 (4560.46ms, 10.7MB)
테스트 2 〉	통과 (4567.11ms, 10.7MB)
테스트 3 〉	통과 (2.30ms, 10.7MB)
테스트 4 〉	통과 (11.32ms, 10.9MB)
테스트 5 〉	통과 (109.21ms, 10.7MB)
테스트 6 〉	통과 (5.24ms, 10.8MB)
테스트 7 〉	통과 (2.48ms, 10.8MB)
테스트 8 〉	통과 (23.77ms, 10.9MB)
'''

특이하게 풀어보고 싶어서 비트 연산자를 사용했습니다. 
numbers의 개수가 3인 경우 이진수  111, 110, 101, 100, 011, 010, 001, 000를
이용해서 1 또는 0이 나온 자리의 원소를 + 또는 - 하면서 조합을 만드는 방식입니다. 

재귀를 이용하는 방식보단 많이 늦군요.. ㅜㅜ
코테에 속도가 중요하지 않지 말입니다. 
https://namu.wiki/w/IOCCC

자바스크립트

function solution(numbers, target) {
	let answer = 0;
	for (let i = (1 << numbers.length) - 1; i >= 0; i--) {
		let total = 0
		let checker = i
		for (let j = numbers.length - 1; j >= 0; j--) {
			let divisor = 1 << j;
			if (parseInt(checker / divisor) == 1)
				total += numbers[numbers.length - j - 1]
			else
				total -= numbers[numbers.length - j - 1]
			checker %= divisor
		}
		if (total == target) answer++
	}
	return answer;
}
/*
테스트 1 〉	통과 (427.75ms, 43.7MB)
테스트 2 〉	통과 (430.29ms, 43.6MB)
테스트 3 〉	통과 (4.07ms, 37.6MB)
테스트 4 〉	통과 (5.21ms, 38.1MB)
테스트 5 〉	통과 (16.37ms, 42.1MB)
테스트 6 〉	통과 (4.78ms, 37.8MB)
테스트 7 〉	통과 (3.99ms, 37.7MB)
테스트 8 〉	통과 (7.90ms, 39.1MB)
*/

당연한 이야기지만 파이썬의 for문이 좀 특이 합니다.
다른 언어들의 for 문에서는 for 문 안에서 index에 변형을 주면 꼬여 버리는데..
(변형된 것에 -- ++ 등을 해주면서 안드로메다로 휘리릭...)
파이썬의 for 문은 뒤에 range 함수에서 숫자를 하나씩 꺼내는 개념이라서
(정확하겐 구글에서 iterable range python을 검색해보시길..)
for 문 내에서 index에 장난을 쳐도.. for 문을 만나면 정상적(?)으로 다음 숫자가 튀어나옵니다..
(기본적으로 foreach 개념이니까...) 
사실 저 위의 파이썬 예제에서는 한 줄을 줄이기 위해 checker를 그렇게 돌려막기를 합니다. 
사실 좋은 코딩은 아니죠. 다른 언어 사용하는 사람에게도 직관적으로 이해할 수 있도록 어느 정도는 맞춰줘야 ...
하지만 코드 뽐내기는 한줄을 줄이기 위해.. 최대한 응용, 노오력...

Java

class Solution {
    public int solution(int[] numbers, int target) {
        var answer = 0;
        for (var i = (1 << numbers.length) - 1; i >= 0; i--) {
            var total = 0;
            var checker = i;
            for (var j = numbers.length - 1; j >= 0; j--) {
                var divisor = 1 << j;
                if (checker / divisor == 1)
                    total += numbers[numbers.length - j - 1];
                else
                    total -= numbers[numbers.length - j - 1];
                checker %= divisor;
            }
            if (total == target) answer++;
        }
        return answer;
    }
}
/*
테스트 1 〉	통과 (233.63ms, 50.3MB)
테스트 2 〉	통과 (233.43ms, 52.7MB)
테스트 3 〉	통과 (1.32ms, 52.2MB)
테스트 4 〉	통과 (2.80ms, 53.1MB)
테스트 5 〉	통과 (12.24ms, 52.7MB)
테스트 6 〉	통과 (2.17ms, 50.1MB)
테스트 7 〉	통과 (1.29ms, 52.1MB)
테스트 8 〉	통과 (4.35ms, 50.3MB)
*/

Kotlin

class Solution {
    fun solution(numbers: IntArray, target: Int): Int {
        var answer = 0
        for (i in (1 shl numbers.size) - 1 downTo 0) {
            var total = 0
            var checker: Int = i
            for (j in numbers.indices.reversed()) {
                val divisor = 1 shl j
                if (checker / divisor == 1) {
                    total += numbers[numbers.size - j - 1]
                } else {
                    total -= numbers[numbers.size - j - 1]
                }
                checker %= divisor
            }
            if (total == target) answer++
        }
        return answer
    }
}
/*
테스트 1 〉	통과 (238.08ms, 59.5MB)
테스트 2 〉	통과 (222.73ms, 57.3MB)
테스트 3 〉	통과 (3.60ms, 59.2MB)
테스트 4 〉	통과 (5.45ms, 59.3MB)
테스트 5 〉	통과 (13.48ms, 57.2MB)
테스트 6 〉	통과 (3.43ms, 59MB)
테스트 7 〉	통과 (2.85ms, 57.3MB)
테스트 8 〉	통과 (8.53ms, 57.5MB)
*/

코틀린의 비트연산자는 신기합니다. 

C#

public class Solution
{
    public int solution(int[] numbers, int target)
    {
        var answer = 0;
        for (var i = (1 << numbers.Length) - 1; i >= 0; i--)
        {
            var total = 0;
            var checker = i;
            for (var j = numbers.Length - 1; j >= 0; j--)
                {
                var divisor = 1 << j;
                if (checker / divisor == 1)
                    total += numbers[numbers.Length - j - 1];
                else
                    total -= numbers[numbers.Length - j - 1];
                checker %= divisor;
            }
            if (total == target) answer++;
        }
        return answer;
    }
}
/*
테스트 1 〉	통과 (255.49ms, 56.9MB)
테스트 2 〉	통과 (255.31ms, 54.9MB)
테스트 3 〉	통과 (12.15ms, 54.6MB)
테스트 4 〉	통과 (13.78ms, 59MB)
테스트 5 〉	통과 (19.22ms, 58.7MB)
테스트 6 〉	통과 (13.25ms, 56.8MB)
테스트 7 〉	통과 (12.07ms, 54.3MB)
테스트 8 〉	통과 (14.03ms, 58.4MB)
*/

GO

func solution(numbers []int, target int) (answer int) {
	for j := (1 << uint(len(numbers))) - 1; j >= 0; j-- {
		total := 0
		for check, i := j, len(numbers)-1; i >= 0; i-- {
			divisor := 1 << uint(i)
			if int(check/divisor) == 1 {
				total += numbers[i]
			} else {
				total -= numbers[i]
			}
			check %= divisor
		}
		if total == target {
			answer++
		}
	}
	return
}
/*
테스트 1 〉	통과 (293.23ms, 9.12MB)
테스트 2 〉	통과 (293.23ms, 9.09MB)
테스트 3 〉	통과 (0.23ms, 9.19MB)
테스트 4 〉	통과 (0.84ms, 9.13MB)
테스트 5 〉	통과 (6.94ms, 7.18MB)
테스트 6 〉	통과 (0.42ms, 9.2MB)
테스트 7 〉	통과 (0.19ms, 9.52MB)
테스트 8 〉	통과 (1.76ms, 11.1MB)
*/