프로그래머스 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

레벨 1 문제들만 풀다가 오랜만에 레벨 2 문제를 건드려봤다. 대놓고 분류가 DFS/BFS로 되어있었으니 망정이지 아니었으면 풀이 방향도 잡지 못했을 것 같다...

풀어내고 다른 사람의 풀이를 보니 200여 명이 열광하는 코드가 떡하니 나와있었다. 그 코드는 정말... 아름다웠다! 재귀를 정말 아름답게 사용했다고 나는 생각한다. 그래서 일단 나의 풀이를 먼저 적어보고 그다음 재귀 풀이를 파헤쳐보자.

나의 풀이

일단 나는 DFS/BFS 문제라고 하니까 바로 트리를 생각했다. 일반적인 트리 구조가 필요했다면 C++ 언어로 트리 구조를 만들었던 기억을 살려 풀으려 했다. 하지만 이 문제는 이진트리의 형태로 풀 수 있다고 생각했고, Full Binary Tree 형태를 가질 것이라 생각했다. Full Binary Tree의 형태면 파이썬의 list 자료 구조를 가지고 쉽게 구현할 수 있기 때문에 따로 이진트리 자료 구조를 만들지 않고 list를 사용했다.

위의 그림처럼 이진트리를 리스트처럼 생각해서 진행할 수 있다. 여기서 주목해야 할 숫자들이 있다. 왼쪽 서브 트리와 오른쪽 서브 트리가 나눠지는 기준, 레벨이 시작되는 인덱스와 레벨이 끝나는 인덱스를 알아야 for문의 반복 범위를 쉽게 정할 수 있다. 이러한 숫자들은 이진트리의 특성 덕분에 2의 거듭제곱으로 나타낼 수 있다. 아래에 위의 그림 속 몇 가지 적어보았다.

인덱스	1	2	3	6	7	14
2의 거듭제곱	2**1 - 1	2**2 - 2	2**2 - 1	2**3 - 2	2**3 - 1	2**4 - 2

이 정도를 머리속에 담아두고 이제 내가 이걸 어떻게 풀었는지 흐름을 알아보자.

순서

1. 이진 트리의 레벨은 0으로 설정하고, 이진트리는 숫자 0을 가지고 있는 루트 노드만 생성한다.
2. while문을 시작할 때마다 트리의 레벨을 올리고, numbers에서 연산에 사용할 숫자(node_num)를 가져온다.
3. 레벨 1의 경우에는 계산이 필요가 없으므로(루트 노드가 0이기 때문에) node_num과 -node_num을 트리에 추가한다.
4. 레벨 2 이상의 경우는 그 전 레벨의 인덱스 범위만큼 for문을 돌며 각 노드 별로 node_num과 -node_num을 더한 값을 트리에 추가한다.
5. while문이 끝나면 leaf node들의 인덱스 범위 안에서 target과 같은 값을 가진 노드의 개수를 센다.

순서를 파이썬 코드로 표현한 것이 아래의 코드다.(이 글을 쓰는 순간까지 계속 수정했다는건 비밀...)

def solution(numbers, target):
    tree_lvl = 0
    binary_tree = [0]
    while len(numbers) > 0:
        tree_lvl += 1
        node_num = numbers.pop()
        if tree_lvl == 1:
            binary_tree.extend([node_num, -node_num])
        else:
            for i in range(2**(tree_lvl - 1) - 1, 2**tree_lvl - 1):
                binary_tree.extend([binary_tree[i] + node_num, binary_tree[i] - node_num])
    return binary_tree[2**tree_lvl - 1 : 2**(tree_lvl + 1) - 2].count(target)

프로그래머스 채점 서버에서 채점한 결과 자원을 최대 226.56ms, 66.9MB만큼 사용했다.

numbers는 최대 20개의 값이 있기 때문에 트리에 계속 값들을 추가하면 최대 2**21 - 1(그냥 2M) 개만큼의 값이 트리에 존재하게 된다....

다른 사람의 풀이

이 풀이를 따라 문제를 푸는 순간, 이 풀이의 아름다움을 느껴버렸다... 아마 이 코드를 생각해낸 사람은 천재이지 않을까 싶다. 아래의 사이트에서 가져온 코드다.

https://programmers.co.kr/learn/courses/30/lessons/43165/solution_groups?language=python3 

프로그래머스

이 풀이의 핵심은 target 넘버에서 더하고 빼고를 반복해서 0이 되는 경우를 센다는 것이다. 나와 정반대로 생각했다!

코드는 아래와 같다. 프로그래머스 채점 서버에서 채점한 결과 자원을 최대 372.24ms, 10.3MB 만큼 사용했다.

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

재귀로 흐름 따라가보기

처음에 딱 보고 바로 흐름을 이해하기 힘들었다. 그래서 하나하나 재귀를 따라가 보며 이해해보기로 했다.

프로그래머스의 예시와 같이 numbers = [4, 1, 2, 1], target = 4라고 하자.

1. 첫 번째 solution 호출: numbers는 비어있지 않고, target도 0이 아니므로 else문에 빠진다.
2. 두 번째 ~ 네 번째 solution 호출: numbers(=[1, 2, 1])는 비어있지 않으므로 else문에 빠진다.
3. 다섯 번째 solution 호출: numbers(=[])는 비어있지만 target은 -4이므로 0을 리턴한다. -> 이 경우는 0이 되는 경우가 아니었다!

이런 식의 재귀 호출을 반복해서 target == 0을 만족하는 경우, 1을 리턴해서 경우의 수들의 합을 최종적으로 리턴하는 구조다.

 

내 풀이와 재귀 풀이의 시간과 메모리 사용량을 비교하면, 내 풀이가 약 150ms 빠르고 약 6배만큼 메모리를 더 사용한다.

재귀 풀이는 함수 호출의 횟수 때문에 시간은 느려진 것 같다. 그리고 numbers [1:] 등으로 함수 호출마다 리스트를 생성하게 된다. 하지만 리스트의 최대 길이는 처음의 numbers의 길이이기 때문에 20이다. 내 풀이에서의 최대 길이랑 비교하면.... 그만 비교하자...

 

레벨 2 문제를 나 혼자서 풀어냈다는 것에 감격스럽지만 재귀 풀이를 보니 나는 아직 갈 길이 멀다!