문제 설명
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 | target | return |
|---|---|---|
| [1, 1, 1, 1, 1] | 3 | 5 |
풀이(이중 for loop 활용)
-
경우의 수를 모두 구하는 문제다. 처음 접근했던 풀이 방법은 이중
for loop를 사용하는 것이었고, 다음과 같은 코드로 어찌저찌 문제를 풀 수 있었다. -
풀이에 대해 간단히 설명하자면, 첫 번째
for loop로 주어진 배열 numbers의 요소를 순회시키고, 두 번째for loop에서 순회하는 요소를 더할 경우의 값과 뺄 경우의 값을 각각 구한 후, 새로 생성한 배열에 담는 것이었다. 이러한 방식으로 배열 numbers를 전부 순회하고 나면, 총 5회(len(numbers)의 길이)에 걸쳐 연산이 이뤄진 모든 결괏값이 담긴 배열이 만들어진다.
def solution(numbers, target):
answer = 0
number_of_cases = [0]
for num in numbers:
calculate_result = []
for case in number_of_cases:
calculate_result.append(case+num)
calculate_result.append(case-num)
number_of_cases = calculate_result
for case in number_of_cases:
if case == target:
answer += 1
return answer
- 하지만 이러한 풀이법은 문제가 의도하는 깊이/너비 우선 탐색(DFS/BFS)을 응용하지 않았다는 점에서 한계가 있을 수밖에 없다. 그래서 DFS/BFS를 활용한 풀이를 해보기로 했다. 필자의 경우, 너비 우선 탐색(BFS)을 활용했으므로, 너비 우선 탐색에 대해서만 다루도록 하겠다.
너비 우선 탐색(BFS)이란?
-
BFS의 개념을 간단히 살펴보면 아래와 같다.
-
시작 정점(루트 노드, 혹은 다른 임의의 노드)으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
-
자세한 설명은 이곳을 참고하면 된다: 참고 사이트
-
-
BFS의 특징
-
깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
- 즉, 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
-
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
- Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
- 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
- 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
-
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
- 즉, 선입선출(FIFO) 원칙으로 탐색
- 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
-
풀이(BFS)
-
우선 자료 구조 queue를 활용해야 하므로, 모듈 deque를 활용해 queue 객체를 만들어주자.
-
요소를 튜플 형태로 만드는 까닭은, 경우의 수(덧셈과 뺄셈 연산으로 얻어진 노드)의 level(깊이)을 나타내기 위함이다.
-
노드의 level이
len(numbers)와 일치한다는 것은, 해당 노드가 numbers의 모든 요소를 더하거나 빼서 얻어진 결괏값임을 의미하기 때문이다. -
level은 numbers의 요소를 꺼내는 인덱스로도 사용된다는 점을 주의하자!
- 즉,
IndexError가 발생하지 않도록 예외처리에 신경써야 한다는 뜻이다.
- 즉,
-
from collections import deque
def solution(numbers, target):
answer = 0
queue = deque([(0,0)]) # sum, idx(level)
return answer- 다음으로, 선입선출(FIFO) 원칙에 따라, queue의 첫 번째 요소를 꺼내자. 이때, 꺼낸 요소(튜플 형태)는 unpacking으로 각각 변수 num_sum과 idx에 할당한다.
from collections import deque
def solution(numbers, target):
answer = 0
queue = deque([(0,0)]) # sum, idx(level)
num_sum, idx = queue.popleft()
return answerqueue객체의 요소가 모두 제거(out)되어 비어있을 때까지 순회가 계쏙되어야 하므로while queue:로loop를 만들어 준다.
from collections import deque
def solution(numbers, target):
answer = 0
queue = deque([(0,0)]) # sum, idx(level)
while queue:
num_sum, idx = queue.popleft()
return answer- 이제, idx를 이용하여
numbers의 요소를 차례대로 꺼낸후, 해당 요소를queue에서 제거된 요소에 더하거나 뺀 값을 생성한 뒤, queue 객체에 추가(in)한다.
from collections import deque
def solution(numbers, target):
answer = 0
queue = deque([(0,0)]) # sum, idx(level)
while queue:
num_sum, idx = queue.popleft()
num = numbers[idx]
queue.append((num_sum + num, idx + 1))
queue.append((num_sum - num, idx + 1))
return answer-
여기까지 완성되면
queue객체 안에는, 각각의 level에 해당하는 모든 경우의 수가 추가되고, 제거되는 작업이 반복된다. 언제까지?numbers[idx]에서IndexError가 발생할 때까지이다. -
남은 작업은 크게 두 가지다. 하나는
queue의 요소가 level이 5인 경우에,num_sum이target과 일치하는 지를 확인하여answer값을 증가시키는 것. 다른 하나는numbers[idx]에서IndexError가 발생하지 않도록 예외 처리를 하는 것이다. 다양한 방식이 있을 수 있는데, 필자는 아래와 같이 처리했다. -
continue를 활용하면,queue객체에 더 이상, 추가(in)는 이뤄지지 않고, 출력(out)만 이뤄지게 된다.
from collections import deque
def solution(numbers, target):
answer = 0
queue = deque([(0,0)]) # sum, idx(level)
while queue:
num_sum, idx = queue.popleft()
if idx == len(numbers):
if num_sum ==target:
answer += 1
continue
else:
continue
number = numbers[idx]
queue.append((num_sum + number, idx+1))
queue.append((num_sum - number, idx+1))
return answer
reviews
- 자료 구조 Queue 활용 방법을 간단하게 일반화하면 다음과 같다.
- Queue 자료 구조의 첫 번째 값을 제거(out)
- 출력된 값을 문제에서 요구하는 바에 따라 처리
- 처리한 값을 Queue 자료 구조에 추가(in)
- Queue 자료 구조의 모든 요소가 제거될 때까지 위 작업을 반복
def solution(numbers,target):
result = {0: 1}
for number in numbers:
temp_result = {}
for num, count in result.items():
temp_result[num+number] = temp_result.get(num+number, 0) + count
temp_result[num-number] = temp_result.get(num-number, 0) + count
result = temp_result
return result.get(target)