[프로그래머스] '타겟 넘버' 문제 풀이

 

 

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

---

문제 설명

주어진 정수 배열을 적절히 더하거나 뺀 값이 주어진 타겟 넘버와 같은 경우의 수를 출력

 

풀이법 구상

처음에는 이중 반복문을 돌면서 각 숫자를 음수로 바꾼 후의 총 합이 타겟과 같은지 판별하는 로직으로 구현했다가 실패

-> +4-1+2-1 과 같이 음수 사이에 양수가 존재하는 경우는 고려할 수 없음

 

각 숫자가 양수이거나 음수인 경우만 고려하면 되고 그러면 2^N의 시간 복잡도가 발생하는데, N의 최대값은 20으로 약 1,050,000이 됨

각 숫자가 양수이거나 음수가 되는 경우를 모두 고려하려면 각 숫자에 +,-를 붙인 노드로 이루어진 트리로 시각화할 수 있음

각 노드를 탐색하며 더한 합계값을 타겟 넘버와 비교하면 결과값 도출 가능

탐색에는 BFS/DFS를 모두 사용할 수 있으나 제출 코드는 BFS사용

 

 

코드 구현 (스위프트 사용)

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var result = 0
    var sum_arr = [0]   // 반복문 시작을 위해 0 하나 추가
    
    for n in numbers {
        var temp: [Int] = []
        for s in sum_arr {
            temp.append(s+n)
            temp.append(s-n)
        }
        sum_arr = temp
    }
    
    for s in sum_arr { result += (s == target) ? 1 : 0 }
    
    return result
}