코딩하고자용 블로그

타겟 넘버 (프로그래머스 level 2 BFS/DFS) 본문

알고리즘 일기/프로그래머스

타겟 넘버 (프로그래머스 level 2 BFS/DFS)

코딩하고자용 2020. 7. 3. 01:49

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

 

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

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+

programmers.co.kr

 

1. 첫번째 풀이 방식(틀린 방식)

def solution(numbers, target):
    answer = 0
    lennum=len(numbers)
    expression = ''#최종 식 들어가는 자리
    for i in range(0,2**lennum):
        ch = bin(i)[2:].zfill(lennum) # 00000,00001, ... ,11110, 11111
        ch = ch.replace('0','-')
        ch = ch.replace('1','+') # -----,----+, ... , ++++-, +++++
        for j in range(0,lennum):
            expression = expression + ch[j] + str(numbers[j])
        confirm = eval(expression)
        if confirm == target:
            answer += 1
        expression = ''
    return answer

예로 [1,1,1,1,1]을 했을 때 

2^5의 모든 경우의 수를 계산해주어서 풀 생각을 하였지만, 이는 꽤나 옳지 못한 생각이었다...

이 문제는 DFS인 트리를 활용하는 것이 핵심이다.

 

2. 두번째 풀이 방식

def solution(numbers, target):
    terminaltree = [0] #최후 단말 노드
    for number in numbers:
        before = []
        for t in terminaltree:
            before.append(t+number)
            before.append(t-number)
        terminaltree = before #단말노드만 alltree에 저장
    return terminaltree.count(target)

 

처음은 0부터 시작하며, A와 -A를 둘 다 트리에 자식으로 넣어 주고 이 결과를 terminaltree에 값을 넣어주는 방식으로 numbers의 갯수만큼 반복시켜주어 최종적으로 2^n개의 결과가 나오는데 이 중 target의 값을 확인해주면 된다.

다시 말하면 A가 before 리스트일 때, B가 terminaltree 리스트의 값들이다.