[프로그래머스] Level2 | 타겟 넘버 - 파이썬(Python) | DFS/BFS

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

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

프로그래머스에서 DFS/BFS 문제인 타겟 넘버를 풀었다.

이코테에서 간단한 문제만 보다가 레벨2인데도 너무 어려웠다.. 더 많이 공부해야할 것 같다 ㅠ

---

혼자 힘으로 풀 수 없어 다른 사람들의 풀이를 참고해서 겨우 풀었다.

사실 이해를 제대로 했는지도 모르겠고 ㅋㅋ...

 

모든 풀이와 개념은 해당 링크 를 참고하였습니다.

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

 

stack을 이용한 DFS 풀이법으로 나는 해결을 했다.

deque를 사용할 생각을 못했는데 stack을 쓰지않고 deque를 사용해도 상관없는 것 같다. 어차피 원리는 같기 때문에!

 

정답 코드

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

내가 이해하고 사용한 건 인덱스 값에 따라 다음 원소가 정해지기 때문에 queue를 사용할 때 인덱스 값을 가지고 가야한다는 것이다.

pop한 temp는 마지막 원소가 되고 타겟 넘버랑 같으면 answer에 1을 더해준다.

 

더 자세히 설명하자니 내가 이 개념을 제대로 이해를 하지 못하고 있는 것 같아서... ㅠ

위에 링크 걸어둔 참고한 블로그에서 개념과 풀이를 정말 잘 설명해주고 있다!!!!

해당 링크

 

 

DFS/BFS는 어렵다고 계속 멀리하고 있었는데 이코테로 개념 복습을 더 하고 더 많은 문제를 풀어봐야할 것 같다...

---

해당 문제 풀이 코드

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비