[프로그래머스] Lv2 - 타겟 넘버

문제

프로그래머스 코딩테스트 고득점 Kit - 깊이/너비 우선 탐색(DFS/BFS)

• Lv 2. 타겟 넘버 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3

코드 구현

def solution(numbers, target):
    answer = 0

    def dfs(index, numbers_sum):
        if (index == len(numbers)):
            if (numbers_sum == target):
                nonlocal answer
                answer += 1
            return

        dfs(index + 1, numbers_sum + numbers[index])
        dfs(index + 1, numbers_sum - numbers[index])

    dfs(0, 0)

    return answer

풀이

• 각 숫자별로 앞 부호가 +인 경우와 -인 경우로 총 2가지 경우를 탐색하며 target에 맞는 합을 찾아낸다면 총 $2^{len(numbers)}$ 만큼의 경우의 수를 탐색하게 된다.
  • 주어지는 숫자의 개수는 20개 이하이므로 시간초과는 나지 않을 것 같아서 DFS로 짜게 되었다.

• DFS 재귀 설계법
  - 수행동작을 먼저 구현
  - 탈출조건 구현
  - 재귀함수 자세히 그려보기
  

• DFS이므로 index값을 계속 전달하면서 재귀를 통해 반복하며 target에 맞는 값일 시, answer ++ 을 해준다.
  • break 조건 : index가 numbers의 길이를 초과하는 값일 시
• 프로그래머스에서 돌아가기 위해서 solution함수 안에서 돌아가는 재귀로 구현하였기 때문에 answer 변수를 전역변수로 사용하고자 nonlocal을 명시해주었다.

What I learned

신박하다고 생각된 정답코드

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)

BFS로 푸는 방법
참고 : https://velog.io/@ju_h2/Python-프로그래머스-level2-타겟넘버-BFSDFS

파이썬에서 전역변수 사용하는 법
참고 : https://juhi.tistory.com/6
▶️ global

n = 1 
def func1(): 
  def func2(): 
    global n
    n += 1 
    print(n) # 2 
  func2() 
func1()

• func2()에서 n 이라는 변수를 지역변수가 아닌 밖에 선언되어 있는 전역변수인걸로 쓰겠다 !
• global로 선언되려면 모든 함수 밖의 전역변수로 선언되어 있어야 함

▶️ nonlocal

def func1(): 
  n = 1 
  def func2(): 
    nonlocal n 
    n += 1
    print(n) # 2 
  func2() 
func1()

• func2()에서 n이라는 변수는 지역변수가 아닌걸 쓰겠다 !
• nonlocal로 선언되려면 해당 함수에 존재하는 지역변수가 아니면 됨