[Algorithm] 타겟넘버

 

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

[12월 20일]

2시간 가량 생각했는데, 잘못된 풀이 방법을 계속 고수하고 있었다. 

다른 사람들의 풀이를 살펴봤다. 제대로 본 건 아니고, 아 이런 개념으로 풀 수 있구나. 오늘은 여기서 끝.

 

[12월 21일]

새로운 마음으로 다시 풀었다. DFS, BFS 개념 다시 돌아보고 코드 다시 보면서 stack, queue 관점으로 다시 생각해봤다. 

1시간이 채 안돼서 풀었다. 어쨌든 모든 것을 다 탐색해야 하니까. DFS, BFS 중 BFS로 풀어보고 싶었다.

어제 잠깐 본 풀이 힌트를 빌렸다. queue.

 

나의 풀이

from collections import deque

def BFS(numbers, target):

  queue = deque()
  queue.append(0)

  for i in range(len(numbers)):
    temp = []
    for element in queue:
      temp.append(element + numbers[i])
      temp.append(element - numbers[i])
    queue = temp[:]

  return queue.count(target)

def solution(numbers, target):
    return BFS(numbers, target)

 

 

다른 풀이

1. product

일단, 처음 알게된 파이썬의 라이브러리 product

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

[1, 3, 2, 4] 라고 가정한다면, 

[(1, -1), (3, -3), (2, -2), (4, -4)] 각 원소에서 하나씩 뽑아 더하고, list를 만든다. 

그 list에서 count를 세주고 있다. 

 

2. DFS / BFS