문제
https://school.programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
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 함수를 작성해주세요.
풀이
def solution(numbers, target):
sup = [0] # 모든 계산 결과를 담자
for i in numbers:
sub = []
# 자손 노드
for j in sup:
sub.append(j + i)
sub.append(j - i)
sup = sub
return sup.count(target)
다른 풀이
a = 0
def dfs(i, result, numbers, target) :
global a
if i == len(numbers) :
if result == target :
a+=1
return
else :
dfs(i+1, result+numbers[i], numbers, target)
dfs(i+1, result-numbers[i], numbers, target)
def solution(numbers, target):
result = 0
dfs(0, result, numbers, target)
return a
설명
1. 원소에 하나씩 접근하면 되겠다는 생각은 했으나, 어떤 방식으로 해야할지 가늠이 오지 않았었음.

## 아이디어
노드 엣지로 구성된 그래프를 그릴 수 있는 상하좌우, map 문제 뿐 아니라 이런 것도 bfs/dfs 문제임을 깨닫게 해준 문제. 이진 트리 형식으로 뻗어나갈 수 있는 문제는 dfs/bfs로 접근할 수 있음을 항상 염두해 두어야겠다.
이 문제의 접근방식을 손그림으로 표현하면 다음과 같다. 가장 main idea는 +, - 부호에 따른 각 숫자에서 2가지 경우의 수가 생산된다는 것이다. 따라서 numbers의 각 숫자에 따라 2가지 경우로 자손을 뻗을 수 있게되고, 모든 경우의 수를 탐색하는 bfs/dfs 문제가 된다.
2. 위의 넓이 우선 탐색을 이용한 것이라고 보면 이해하기 쉽다.
먼저 super node로 [0]을 하나 만들어 두고 [0+1] [0-1] 로 sub node 두개를 생성한다.
이렇게 생성된노드 super node로 저장되고,
저장된 super node는 for문을 돌면서 [0+1+1] [0+1-1] , [0-1+1] [0-1-1] 를 거치면서 super node에 다시 저장된다.
이런 방식으로 전체 저장되는 리스트가
[5, 3, 3, 1, 3, 1, 1, -1, 3, 1, 1, -1, 1, -1, -1, -3, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3, -3, -5]
이 되고 여기에서 target number인 3의 개수를 count 로 찾으면 된다.
'Coding Test > Python' 카테고리의 다른 글
| [프로그래머스] 게임 맵 최단거리 (0) | 2023.08.15 |
|---|---|
| [프로그래머스] 네트워크 (lv.3) (0) | 2023.08.11 |
| [프로그래머스] 모음사전 (lv.2) (0) | 2023.08.08 |
| [프로그래머스] 전력망을 둘로 나누기 (lv2) (0) | 2023.08.05 |
| [프로그래머스] 피로도 (0) | 2023.08.05 |