프로그래머스 레벨2. 타켓 넘버 <오답노트>

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

프로그래머스

쉬울 줄 알았는데 생각보다 어려워서 구현하지 못했다..ㅋㅋ

진짜 언제쯤 레벨2는 눈 감고 풀 수 있을까

 

다른 분들의 풀이를 참고하였다. 나중에 다시 풀어볼 예정이다.

from itertools import product

def solution(numbers, target):
    length = len(numbers)
    # 전체 가능한 case 구하기
    cases = list(product([-1, 1], repeat = len(numbers)))
    print(cases)
    # target 인 경우만 count 하기
    cnt = 0
    for case in cases:
        sum = 0
        for i in range(len(numbers)): #0~4
            sum += case[i] * numbers[i]
        if sum == target :
            cnt += 1
    return cnt

product의 곱합을 이용한 풀이이다. 비효율적인 코드이긴 하지만, 내부 함수 기능을 잘 쓴 것 같아서 가져왔다.

나도 위 코드와 마찬가지로 product를 이용해 [1,1,1,1,1] 부터 [-1,-1,-1,-1,-1] 등등의 모든 케이스를 구했지만, 어떻게 접근해야할지 감이 잡히질 않았다. 

보니깐,  이중반복문 원소 i를 case[i] number[i]에 모두 넣어줘서 모든 케이스를 다 돌게 하였다. 

음 이걸 어떤 식으로 적어야할지 모르겠다...........

나는 이중반복문 원소를 case[i]와 numbers[j]로 접근했었는데, 그럼 numbers가 1씩 증가될 때, case는 움직이지 않는다. 즉, case가 0일때, numbers가 0~5까지 다 돌게 돼서 실패하였는데,

그냥 둘 다 j를 넣으면 됐었다.....

 

이제 효율적인 코드를 알아보자.

dfs/bfs를 이용한다.

def solution(numbers, target):
	super = [0]
    for i in numbers:
    	sub = []
        for j in super:
        	sub.append(j+i)
            	sub.append(j-i)
        super = sub #슈퍼노드로 설정   
        
    return super.count(target)

대박이다.........

내가 이걸 생각해낼 수 있을까...?

이해하는데도 한 참 걸 렸 다 . . .