취준/프로그래머스

[프로그래머스 Programmers][Python] 타겟 넘버

puff 2020. 2. 2. 18:00

문제 : 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+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘

programmers.co.kr

BFS로 풀었다.

BFS는 기본적으로 큐를 쓰는데, 파이썬은 deque를 쓰면 편하다.

 

이 문제는 numbers를 하나하나 더하거나 빼면서 target과 같게 할 수 있는 경우의 수를 구하는 문제다.

 

내가 푼 방법은 다음과 같다.

 

  1. 큐 아이템을 (현재 값, 현재까지 탐색한 위치) 로 한다.
  2. 처음에 [-1,0], [1,0] ( 첫번째 값의 +,- 값) 을  큐에 넣는다.
  3. 큐가 빌때까지:
    1. 탐색위치가 numbers 길이가 될 동안
    2. 현재 (+,-) [다음 탐색할 값] 이 target이면:
      1. answer+=1 한다
    3. 아니면 (현재 (+,-) [다음 탐색할 값] , 현재위치+1) 을 큐에 넣는다.

 

from collections import deque

def solution(numbers, target):
    answer = 0
    maxlen = len(numbers)
    q = deque()
    q.append((numbers[0],0))
    q.append((-numbers[0],0))

    while q:

        cur=  q.popleft()

        if cur[1]+1 < maxlen:
            if cur[0]+numbers[cur[1]+1] ==target and cur[1]+1 == maxlen-1:
                answer+=1
            else:
                q.append((cur[0]+numbers[cur[1]+1] ,cur[1]+1))

            if cur[0]-numbers[cur[1]+1]==target and cur[1]+1 == maxlen-1:
                answer+=1
            else:
                q.append((cur[0]-numbers[cur[1]+1] ,cur[1]+1))

    return answer

 

저작자표시 비영리 변경금지