[알고리즘] 프로그래머스 타겟 넘버 파이썬

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

✅ 문제

✅ 나의 풀이

나는 문제를 읽고 DFS, 그리고 이진트리의 형태가 생각났다. 하지만 정작 완성된 내 코드를 보니 트리와 관련된 알고리즘은 보이지 않는다. 앞으로는 아이디어에 맞게 코드를 작성하는 연습을 해야겠다.

numbers 배열로 받은 수의 양수와 음수를 모두 방문하며 계산하는 방식이다.

1. numbers 배열을 stack에 넣고 계산 (eval) 후 target과 비교 & answer 증가
2. stack의 top이 음수인 경우, 해당 수의 양/음수를 모두 체크했다는 의미이므로 top이 양수가 될 때까지 계속 pop
3. 양수인 top을 pop하고 pop 된 수의 음수를 다시 stack에 삽입

1~3 번 과정을 반복한다. 그렇다면 총 2^len(numbers) 번 계산된다.

def solution(numbers, target):
    answer = 0
    stack = []
    for n in numbers :
        stack.append(n)
        
    while stack:
        ev = eval('+'.join(map(str, stack)))
        if ev == target :
            answer += 1
        while stack and stack[-1] < 0:
            stack.pop()
        if not stack :
            break
        popNum = stack.pop()
        stack.append(-popNum)
        c = len(numbers) - len(stack)
        if c > 0 :
            for i in range(c, 0, -1) :
                stack.append(numbers[len(numbers)-i])
    return answer

굉장히 난잡하지만.. 다 풀고 최적화할 생각이었어요.. 엉엉
하지만 두 케이스가 시간 초과로 넘어가지 못해서 포기해버린 알고리즘 🥲
검색해보니 eval()을 사용해서 풀이한 사람은 극히 드물었다. 느린 함수라고 한다. 그리고 이것이 시간 초과의 이유인 듯 하다.

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    def dfs(idx, result):
        nonlocal n
        nonlocal numbers
        if idx >= n - 1 :
            if result == target :
                nonlocal answer
                answer += 1
            return
        idx += 1
        dfs(idx, result + numbers[idx])
        dfs(idx, result - numbers[idx])
        return
    
    dfs(-1, 0)
    return answer

검색을 통해 재귀함수 사용하는 알고리즘으로 재구현.
재귀함수를 사용하면 굳이 전체 식을 계산하지 않고 하나씩 계산해나갈 수 있다는 사실을 간과했다. 무조건 트리의 끝에 도달하면 계산해야지! 라는 생각으로 eval()을 쓴 듯 하다.

어쨌든 키포인트는,

• 인덱스와 계산결과를 전달해가며 계산하기
• 인덱스가 트리의 끝부분에 도달 시 target과 값 비교 후 return하기

✅ 다른 풀이

내가 원했던 DFS 스택 사용하는 풀이

def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0],0]]
    n = len(numbers)
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

BFS 알고리즘과 deque 사용한 풀이

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

출처는 여기

✅ 얻어가기

eval()

문자열 타입의 수식을 계산해주는 함수인데 속도가 느리다. 사용을 자제하자.

list에 원소 추가하기

• append(value) : 맨 끝에 하나 추가
• extend([iterable]) : 연결
• insert(index, value) : 위치 지정 가능