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

프로그래머스의 코딩연습 중 level2의 DFS/BFS 카테고리의 "타겟넘버" 문제 풀이

(문제 : 아래 링크👇👇👇)

프로그래머스

 

문제풀이

 

처음 접근 방식 (정확성 75%, 테케 1,2번 시간초과로 통과 못함)

나의 경우는 처음 두 테케에서 시간초과가 떴다.

접근 방식은 주어진 numbers 길이만큼 '+','-'로 가질 수 있는 모든 경우에 대해서 생성해주고 이를 numbers에 붙여주는 것이었다. (itertools의 product함수를 사용)

예를 들어, [4,1,2,1] 가 numbers로 주어진다면,

'+'와 '-'로 이루어진 길이가 4개의 모든 경우의 수를 구한다.

('+', '+', '+', '+') ('+', '+', '+', '-') ('+', '+', '-', '+') ('+', '+', '-', '-') ('+', '-', '+', '+') ('+', '-', '+', '-') ('+', '-', '-', '+') ('+', '-', '-', '-') ('-', '+', '+', '+') ('-', '+', '+', '-') ('-', '+', '-', '+') ('-', '+', '-', '-') ('-', '-', '+', '+') ('-', '-', '+', '-') ('-', '-', '-', '+') ('-', '-', '-', '-')

그리고 이들 각각을 numbers의 element 각각과 concat하고 string으로 바꿔주고 eval함수를 통해 그 값이 target과 같은지 아닌지 판단..!

코드

반응형

############# 정확성 : 75% #############
from itertools import product
def solution(numbers, target):
    numbers = list(map(lambda x :str(x), numbers))
    cnt = 0
    for i in product('+-', repeat=len(numbers)) :
        concat = list(map(str.__add__,i,numbers))
        if eval("".join(concat)) == target :
            cnt += 1
    return cnt

 

사실 완전탐색으로 코드를 작성한 것이라 틀린 방법이라 할 수는 없지만 시간초과가 뜬 것을 보아 효율적이지 못한 코드인 것.

---

두번째  접근 방식 (정확성 100%)

dfs/bfs 카테고리 문제인데 완전탐색으로 푼게 문제가 됐던 것 같아 dfs/bfs방식으로 접근해봤다.

########## 정확성 100% ##########
def solution(numbers, target):
    global cnt
    cnt = 0
    def dfs(idx,res) :
        global cnt
        if idx == len(numbers) :
            if res == target :
                cnt += 1
            return 0
        res1 = res + numbers[idx]*1
        dfs(idx+1,res1)

        res2 = res + numbers[idx]*(-1)
        dfs(idx+1,res2)
    dfs(0,0)
    return cnt

 

정확성 100%로 통과하긴했지만.. 사실 뭔가 내 맘에 쏙 드는 코드가 아니었음 ㅠㅠ

---

세번째  접근 방식 (정확성 100%)

itertools의 product함수를 좀 더 "잘" 활용해봤다.

######### 정확성 100% #########
from itertools import product
def solution(numbers, target):
    cnt = 0
    num_lst = [[+x,-x] for x in numbers]

    for i in product(*num_lst) :
        if sum(i) == target :
            cnt += 1
    return cnt

풀이를 예시를 들어 해보자.

numbers = [1,2,3]으로 주어진다고 하자.

num_lst = [[1, -1], [2, -2], [3, -3]] 가 된다.

여기서 관건은 우리는 num_lst안에 있는 각 list들에서 원소를 하나씩 뽑아서 조합할 수 있는 모든 경우의 수를 구하는 것이다.

이를 위해 itertools의 product함수를 사용하였고 *operator를 사용해줬다.

따라서 product(*num_lst)를 하게 되면 다음과 같이 나오게 된다.

(1, 2, 3)
(1, 2, -3)
(1, -2, 3)
(1, -2, -3)
(-1, 2, 3)
(-1, 2, -3)
(-1, -2, 3)
(-1, -2, -3)

이 각 결과물들을 sum하여 target과 비교하며 답을 구하는 것...!

 

---

내가 제시한 여러 코드들과 접근방식이 도움이 됐기를 바라면서..!! 마친다 😊