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

코딩테스트 공부하기로 마음먹고 처음 풀어본 문제다.

하지만.. 결과는 처.참.했.다.

검색을 해보니 DFS/BFS 문제로 푼다고 한다. 둘 중 스택을 이용한 DFS로 풀이 하는 것으로 이해했고 풀이했다.

문제 2번째 예시인 numbers가 [4,1,2,1] 인 경우를 생각해봤다.

---

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    # temp, idx 값을 의미
    stack = [[numbers[0], 0], [-1*numbers[0], 0]]
    
    while stack:
        temp, idx = stack.pop()
        idx += 1
        if idx < n:
            stack.append([temp+numbers[idx], idx])
            stack.append([temp-numbers[idx], idx])
        else: # idx >= n
            if temp == target:
                answer += 1
    
    return answer

위 코드를 이해할 때, 꽤 오랜 시간이 걸렸다. 그 이유는 스택의 특징을 놓치고 있었기 때문이다!!!!!😥😥

스택은 마지막에 들어 온 값을 먼저 pop 해주는 것을 알아야 한다!!

 

코드가 이해가 가지 않을 때 아래와 같이 일일이 print 해주면서 비교해보는 것도 하나의 방법이다.

numbers = [4,1,2,1]
answer=0
target = 4
que = [[numbers[0],0], [-1*numbers[0],0]]
n = len(numbers)

while que:
  print('que',que,'\n')
  tmp, idx = que.pop()
  idx += 1
  print('tmp', tmp, 'idx', idx, '\n')
  if idx < n:
    que.append([tmp+numbers[idx], idx])
    print('plus', que, '\n')
    que.append([tmp-numbers[idx],idx])
    print('minus', que,'\n')
  else:
    if tmp == target:
      answer += 1

print('answer=',answer)

---

참고 블로그 url : 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)

 

다음엔.. 혼자 해결해봐야지... 어렵다.... 😫😫