[Python 파이썬] 프로그래머스 - 타겟 넘버

 

2024년 6월 8일

문제 링크 : 프로그래머스 - 타겟 넘버

프로그래머스

 

 

---

문제 접근

 

n개의 수가 주어지면, n개의 " + " 혹은 " - " 연산자를 적절히 섞어 사용해 target과 일치하는 경우가 총 몇 가지 인지 구하는 문제이다.

 

연산자는 2종류 이므로, n이 최대 20일 때 최악의 경우의 수는 2^20 = 1,048,576로 완전탐색해도 되겠다 싶었다.

 

n이 5일 때를 생각해보면 다음과 같이 모든 경우의 수를 생각할 수 있다.

 

 

실제 트리처럼 구현하지는 않았지만, 어떻게 풀까 고민하다 그림을 그려보고 백트래킹으로 접근해 완전탐색을 진행하고자 결정하였다.

 

연산자 조합을 구성하는 연산자 개수가 n개라면 해당 경우로 target의 결과가 나오는지 확인해보고, 마지막에 추가한 연산자를 pop()하여 뺴주고 다른 연산자를 넣고, 해당 경우를 모두 확인해보면 더 이전으로 거슬러 올라가는 로직으로 접근하였다.

 

---

전체 코드

 

# 숫자의 개수는 최대 20개 -> 백트래킹을 통한 완전탐색 경우의 수 : 2^20 -> 시간복잡도 괜찮음

def solution(numbers, target):
    global answer
    global length
    length = len(numbers)
    answer = 0

    back_tracking(numbers, target, [], 0)

    return answer

def back_tracking(numbers, target, ops, seq):
    global answer
    global length
    if seq == length:
        result = 0
        for i in range(seq):
            if ops[i] == "+":
                result += numbers[i]
            else:
                result -= numbers[i]
        if result == target:
            answer += 1
        return
    op = ["+", "-"]
    for i in range(2):
        ops.append(op[i])
        back_tracking(numbers, target, ops, seq + 1)
        ops.pop()

if __name__ == "__main__":
    numbers = [4, 1, 2, 1]
    target = 4

    print(solution(numbers, target))

---

풀이 후기

 

백트래킹은 어떻게 재귀적으로 접근할건지, 초기값을 어떻게 구성하고 어떤 조건에서 결과값을 어떻게 반환할건지 결정하는게 중요하다 생각한다.