[스파르타] 99클럽 2기 코테스터디 11일차 TIL / 타겟 넘버

프로그래머스: 타겟 넘버 (링크)

타겟 넘버

 

BFS 방식으로 어떻게 풀어야 할지 고민하다가 잘 모르겠어서 다른 분의 풀이를 참고했다. 생각보다 간단하게 풀 수 있는 문제였다. 큐에 매번 모든 수의 양수와 음수를 넣고 마지막에 모든 인덱스까지 돌았다면 큐에서 하나씩 꺼내서 타겟과 맞는지 확인하면 된다.

 

예시를 들어보자면 numbers = [4, 1, 2, 1], target = 4 일 때 제일 처음 큐에는 [4, 0], [-4, 0] (=numbers[0], 인덱스)가 들어가게 된다. 이후에 while문을 돌면서 다음 인덱스인 1의 양수, 음수 값도 큐에 넣는다. [5, 1], [3, 1] 이런 식으로 넣고 큐에 남아 있던 [-4, 0]도 꺼내서 [-3, 1], [-5, 1]을 다시 큐에 넣어준다. 이걸 인덱스 끝까지 돌면 큐에는 최종적으로 연산이 끝난 값들만 남게 된다.

 

좀 더 생각해 보면 알 수 있었을 문제였을텐데 매번 응용이 어렵다. 다양한 문제를 풀어보면서 감을 잡아야겠다.

 

from collections import deque

def solution(numbers, target):
    queue = deque()
    n = len(numbers)
    answer = 0
    
    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

오늘 미들러 풀이 끝!

---

참고한 블로그: https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS

[Python] 프로그래머스 level2 타겟넘버 (BFS/DFS)