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

타겟 넘버

출처: 프로그래머스 - 타겟 넘버

문제

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가 [1, 2, 3] 으로 주어졌을때, 이름 덧셈 뺄셈으로 조합할 수 있는 경우는 다음과 같다.

[-1, -2, -3]: -6
[-1, -2, +3]: 0
[-1, +2, -3]: -2
[-1, +2, +3]: 4
[+1, -2, -3]: -4
[+1, -2, +3]: +2
[+1, +2, -3]: 0
[+1, +2, +3]: +6

이는 좀 더 시각적으로 다음과 같이 나타낼 수 있을 것이다.

그림이 좀 조잡하긴 하지만, 어느정도 의미전달은 됐을거라고 생각한다 (과연?)

쉽게 말해 그냥 무식하게 한 단계 아래로 내려갈때마다 각 경우의 덧셈 뺄셈을 다 해보고, 최종 결과를 내는 것이다.

나는 이 컨셉을 다음과 같은 코드로 표현해보았다.

  1 def solution(numbers, target):
  2     cnt = 0
  3
  4     def operator(numbers, target, idx=0):
  5         if idx < len(numbers):
  6             numbers[idx] *= 1
  7             operator(numbers, target, idx+1)
  8
  9             numbers[idx] *= -1
 10             operator(numbers, target, idx+1)
 11
 12         elif sum(numbers) == target:
 13             nonlocal cnt
 14             cnt += 1
 15
 16     operator(numbers, target)
 17
 18     return cnt

(2) 타겟넘버를 카운팅할 변수를 선언

(5) 만약 인덱스번호가 numbers의 전체 길이보다 작다면 (즉, 아직 순회를 모두 마치지 않았다면)

(6, 9) 인덱스에 해당하는 번호에 각각 1과 -1을 곱해주고 (워 그림에서 +, - 기호를 붙여 두개의 자식을 만드는 과정이라고 생각하면 된다)

(7, 10) 인덱스 번호를 하나 증가시켜 다시 operator를 재귀호출한다 (자식을 만들었으니, 이제 자식의 자식을 만들기 위해!)

인덱스 번호를 하나씩 증가시키며 재귀호출하기 때문에, 언젠가는 인덱스가 숫자 리스트의 길이와 같아지는 순간이 올 것이다.

(12) 인덱스가 숫자 리스트의 길이와 같아졌고, (모든 노드를 순회했고,) 숫자 리스트의 합이 타겟넘버와 같다면,

(13~14) 카운트를 하나 증가시켜준다.

이 때, nonlocal 키워드를 사용한 이유는 내부함수인 operator에서 외부함수인 solution의 변수에 접근하기 위함이다.

함수 내부에서 전역변수에 접근할때 global 키워드를 사용하는 것과 같은 맥락이다.

공간 복잡도 개선 (2019/08/25, ‘주향’님 댓글내용 참고)

def solution(numbers, target):
    cnt = 0
    len_numbers = len(numbers)

    def operator(idx=0):
        if idx < len_numbers:
            numbers[idx] *= 1
            operator(idx+1)

            numbers[idx] *= -1
            operator(idx+1)

        elif sum(numbers) == target:
            nonlocal cnt
            cnt += 1

    operator()

    return cnt

댓글 달아주신 ‘주향’님의 의견을 반영해 코드를 조금 개선했다.

기존 코드를 보면 operator에서 numbers, target을 계속 받아오고있다.

하지만 numbers, target은 처음에 solution 함수에서 전달받은 값을 그대로 사용하면 되므로,

operator를 호출할때마다 똑같은 값을 계속 다시 넘겨줄 필요는 없다.

이런식으로 함수 호출시마다 인자를 전달하게되면 호출시마다 계속해서 인자의 복제본을 생성하게된다.

특히 numbers의 경우, 리스트 전체가 계속 복제되는 상황이므로 메모리 효율이 매우 비효율적이다.

또한 len(numbers) 라는 메소드가 operator 실행시마다 계산되는데,

이는 결국 똑같은 값을 계속 사용하는 것이므로, 이를 미리 계산해놓도록 바꾸었다.

분석

여태까지는 어찌보면 직관적이고 단순하게 문제에 접근했었는데,

그래프나 DFS, BFS등의 개념을 생각하며 문제를 풀려니까 머리가 복잡해진다.

그래도 이러한 개념을 아예 모를때에는 솔루션 아이디어조차 떠오르지 않아서 막막했었는데,

개념을 어느정도 익히니 확실히 아이디어는 금방 떠오르는 것 같고, 구현단계에서 고민을 하게되니 한결 낫다.

예전에 거짓말이라는 문제를 풀 때 어떤 사람 풀이중에 그래프 개념을 활용한 것이 있었는데,

그때는 코드도 이해되지 않고 문제만 해결하면 된다는 생각이 있었기때문에 무심코 넘어갔었다.

물론 반드시 어떤 문제에는 어떤 개념을 활용해서 풀어야 한다는 절대적인 규칙같은것은 없지만,

그래도 여러 개념을 두루두루 익혀놓으면 보다 효율적인 접근법이 수월하게 떠오른다는 강점이 생기는 것 같다.

너무 개념에 매몰되지는 말되, 유사시 떠올릴 수 있을 정도까지는 이것저것 다양하게 익혀보자.

• 내용추가 (2019/08/25)

거의 반년 전에 작성한 코드여서 까맣게 잊고 있었는데,

주향님께서 댓글로 피드백을 주신 덕분에 예전에 짰던 코드를 리팩토링할 기회가 생겼다.

이렇게 피드백을 받으니 그것을 개선하는 과정에서 정말 도움이 많이 되고 감사한 마음이 들었다.

여태까지는 다른 사람의 작업에서 개선사항이 발견되어도 귀찮아서 그냥 넘어갔었는데,

짧막하게나마 한줄씩이라도 피드백을 주는 습관을 들여야겠다!

코딩장이

-장이: [접사] ‘그것과 관련된 기술을 가진 사람’의 뜻을 더하는 접미사.

Share Share