[프로그래머스] 타겟 넘버 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

 

1. -1+1+1+1+1 = 3
2. +1-1+1+1+1 = 3
3. +1+1-1+1+1 = 3
4. +1+1+1-1+1 = 3
5. +1+1+1+1-1 = 3

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

 

 

 

제한사항

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

 

 

입출력 예

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

 

 

알고리즘 분석

 

• 나의 풀이

from itertools import product

def solution(numbers, target):
	ans = 0 
	_numbers = list(map(lambda x: -x, numbers))
	zip_n = zip(numbers, _numbers)
	a = list(product(*zip_n))
	for i in a: 
		if sum(i) == target: 
			ans += 1
	return ans 

 

 

 

• Most 1의 풀이

이 코드는 재귀함수를 이용한 코드인데, 이런 방식을 사용했다는게 굉장히 놀라웠다. 

def solution(numbers, target):
    if not numbers and target == 0: # number의 요소가 없고, target이 0이면 1을 반환 
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

마지막 코드를 살펴보면 다음과 같이 동작한다. 

 

현재 numbers의 인덱스 0에 존재하는 값 target에 더하거나 뺀 값을 target으로 삼고,

numbers의 인덱스 1부터의 값들을 numbers로 삼은 solution을 다시 호출한다. 
   

[1,2,3,4,5], 5를 대입한다면,     

sol([1,2,3,4,5], 5)의 경우
return sol([2,3,4,5], 4) + sol([2,3,4,5],6)

sol([2,3,4,5], 4)의 경우
return sol([3,4,5],2) + sol([3,4,5],6)

sol([3,4,5], 2)의 경우
return sol([4,5],-1) + sol([4,5],5)

sol([4,5],-1)의 경우
return sol([5],-5) + sol([5],3)

return sol([],-10) + sol([], 0) 

return 0 + 1 

위와 같은 방식으로 동작할 것이다. 

       

return sol([],-10) + sol([], 0) 을 확인해보자

 

재귀함수가 끝나는 조건은 numbers가 []이 되는 것이고, 

target이 0일 경우 1, 아닐 경우 0을 반환한다. 

 

그렇다면 sol([],-10) 과 sol([], 0)은 어떤 경우의 수를 나타내는 것일까? 

 

재귀함수의 마지막에서 target은 [초기의 target] - [numbers의 합] 을 나타낸다.

 

즉, 

sol([], -10) : 5 - 15 = -10을 근거로 numbers = [1,2,3,4,5] 일 경우를 나타냄 

sol([], 0) : 5 - 5 = 0을 근거로 numbers = [1,2,3,4,-5] 일 경우를 나타냄 

 

결과적으로 target과 numbers의 합이 일치하는 경우, 1을 리턴하여 더하게 되면 원하는 값을 얻을 수 있다.         

 

 

 

• Most 2의 풀이

내 코드와 같은 방식으로 동작하지만 좀 더 코드를 간결하게 만들었다. 

 

from itertools import product # 두 개 이상의 리스트의 조합을 구하는 product 
def solution(numbers, target):
    l = [(x, -x) for x in numbers] # numbers의 모든 요소를 -numbers와 튜플로 묶어서 리스트로 반환
    s = list(map(sum, product(*l))) # l을 이용한 모든 조합의 합들을 list로 s에 대입
    return s.count(target) # s의 요소 중 target과 일치하는 값의 개수를 반환 

 

---