문제

풀이

• 이 문제는 주어진 입력의 조합이 가능한 모든 경우의 수를 탐색해야 하므로 그래프 문제이다.
• 모든 조합을 탐색해야 하므로 BFS/DFS 여부는 중요하지 않다.
  • BFS를 구현하면 단방향 큐를 사용할 수 있고, DFS를 구현하면 스택을 사용할 수 있다. 혹은 재귀를 사용할 수도 있다.
• 입력값의 개수가 제한되어 있으므로 그 개수를 인덱스로 삼아 탐색해나가고 종료조건을 잘 설정해주면 된다.

Trial 1st 풀이

나는 스택을 사용했다. 우선 시작 포인트를 초기화해준다.

stack = [[numbers[0],0], [-1*numbers[0],0]]

이후 스택에서 하나씩 pop 하고 해당 값에 +, - 연산한 결과를 다시 스택에 넣어준다. 이 문제에서는 브랜치 선택지가 +, - 단 2개 뿐이므로 이렇게 구현할 시 연산 하나의 방향으로 깊게 들어가고 종료 조건에 안 맞으면 돌아나오게 된다.

idx 변수 이용하여 입력 길이와 동일하면 타겟 넘버와 비교하게 만들었다. 비교식으로 넘어간다는 건, 해당 브랜치의 제일 깊은 곳까지 도달했다는 뜻이므로 브랜치 확장의 종료조건이 된다.

이를 코드로 구현하면 다음과 같다.

def solution(numbers, target):
    answer = 0
    
    # 연산 배열을 명시적으로 저장할 스택 정의
    stack = [[numbers[0],0], [-1*numbers[0],0]]

		# DFS 탐색 시작
    while stack:
        tmp, idx = stack.pop()
        idx += 1
        if idx < len(numbers):
            stack.append([tmp+numbers[idx], idx])
            stack.append([tmp-numbers[idx], idx])
        else:
						# 브랜치 확장 종료, 타겟 넘버를 만나면 저장
            if tmp==target:
                answer += 1                
    return answer

Trial 2nd 풀이

프로그래머스 사이트에서 다른 사람 풀이를 보다가 스택을 이용한 완전 탐색 풀이가 인상 깊어서 가져왔다.

def solution(numbers, target):
    q = [0]
    for n in numbers:
        s = []
        for _ in range(len(q)):
            x = q.pop()
            s.append(x + n)
            s.append(x + n*(-1))
        q = s.copy()
    return q.count(target)

• 1, -1 에서 시작해서 pop 하면서 매번 각 값에 대한 +, - 을 다시 넣는 구조이다.
• 입력값 개수만큼 돌면서 모든 경우의 수를 q에 저장한다.
• 모든 조합의 결과가 저장된 리스트에서 타겟 넘버가 몇 개인지 센다.

copy 메소드는 [] 리스트를 그대로 복사한다.
count 메소드는 문자열 및 iterable한 자료형에서 주어진 요소의 개수를 반환한다. (dict, set 자료형에서는 사용 불가하다)