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

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

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

 

문제를 해석해 보면 n개의 음이 아닌 정수들이 주어진다. 이 정수 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟넘버를 만드는 문제이다. 예를 들면

 

[1,1,1,1,1]과 타겟넘버 3이 주어지면

 

-1 + 1 + 1 + 1 + 1 -> 3

과 같은 경우를 말하는 것이다. 즉, 주어진 정수들에 대해 부호반전을 해준 정수 리스트와 주어진 리스트 두개를 가지고  타겟넘버를 만족하는 모든 경우의 수를 반환하는 solution()함수를 구현하면 된다.

 

1. DFS를 통한 구현

DFS 방법을 사용해보자

from typing import MutableSequence

def dfs(graph,index,target,sum,answer):
    for i in graph[index]:
        if (index == len(graph) - 1):
            if (sum + i == target):
                answer.append(1)
            continue
        dfs(graph,index + 1, target, sum + i,answer)

def solution(numbers : MutableSequence,target : int):
    answer = []
    graph = [(x,-x) for x in numbers]
    #graph = list(zip(numbers,list(map(lambda x:x * -1,numbers)))) #굳이 안해도되는뻘짓
    # Result : [(1, -1), (1, -1), (1, -1), (1, -1), (1, -1)] 형태의 그래프 생성
    dfs(graph,0,target,0,answer)
    return len(answer)

answer를 Mutable Sequence로 한 이유는, count전역 변수를 사용하지 않게하기 위해서이다. 다만 이로 인해 코드가 난잡해진다는 단점이 있다.

 

2. 조합을 이용한 방법

결론적으로 문제를 보면 (x, -x)형태의 원소들이 담긴 리스트에서 각 요소들의 조합을 통해서 타겟넘버를 만족하는 쌍을 찾아도 되는 문제이다. itertools의 product를 사용하면 두개 이상의 리스트에 대해 모든 조합을 구할때 사용된다.

from itertools import product

def solution(numbers,target):
    number_list = [(x,-x) for x in numbers]
    '''
    product(*number_list)
    -> [(1, 1, 1, 1, 1), (1, 1, 1, 1, -1), (1, 1, 1, -1, 1), (1, 1, 1, -1, -1), (1, 1, -1, 1, 1), (1, 1, -1, 1, -1), (1, 1, -1, -1, 1), (1, 1, -1, -1, -1), (1, -1, 1, 1, 1), (1, -1, 1, 1, -1), (1, -1, 1, -1, 1), (1, -1, 1, -1, -1), (1, -1, -1, 1, 1), (1, -1, -1, 1, -1), (1, -1, -1, -1, 1), (1, -1, -1, -1, -1), (-1, 1, 1, 1, 1), (-1, 1, 1, 1, -1), (-1, 1, 1, -1, 1), (-1, 1, 1, -1, -1), (-1, 1, -1, 1, 1), (-1, 1, -1, 1, -1), (-1, 1, -1, -1, 1), (-1, 1, -1, -1, -1), (-1, -1, 1, 1, 1), (-1, -1, 1, 1, -1), (-1, -1, 1, -1, 1), (-1, -1, 1, -1, -1), (-1, -1, -1, 1, 1), (-1, -1, -1, 1, -1), (-1, -1, -1, -1, 1), (-1, -1, -1, -1, -1)]
    '''
    sum_combinations = list(map(sum, product(*number_list)))
    return sum_combinations.count(target)