[Python] 타겟 넘버

1. 문제

*숫자들의 순서는 고정되어 있다고 생각해야 함.

 

 

 

2. 풀이 과정

방법 1)

1. 배열 정렬하기 => 필요 없는 연산 줄이기 위함

2. 초기설정 : Q를 초기화해 주는 것, 현재 index가 i인 값이 음수가 되어도 좌항의 합이 target값보다 크거나 같은 값만 Q에 넣는다.

3. Q에서 element를 하나 꺼내고 그 element에 기록된 index의 뒤의 값들이 또 음수가 되어도 좌항의 합이 target값보다 크거나 같은 값만 Q에 넣어준다.

4. Q의 element는 (음수 처리한 마지막 인덱스 값, 좌항의 합)로 구성되는데, 좌항의 합이 target이면 결과로 출력할 count += 1을 하고 다음 요소를 처리하러 간다.

from collections import deque
def solution(numbers, target):
    l =len(numbers)
    numbers.sort()
    total = sum(numbers)
    
    Q = deque() #index, 선택한 수의 배열
    #초기 설정
    for i in range(l):
        if total - 2 * numbers[i] < target: #음수로 바꾸기 = 두 번빼야함
            break
        Q.append((i, total - 2*numbers[i]))
    #
    result = 0
    while Q:
        idx, t = Q.popleft()
        if t == target:
            result += 1
            continue
        for i in range(idx+1, l):
            if t - 2*numbers[i] >= target:
                Q.append((i, t - 2*numbers[i]))
            
    return result

 

방법 2) 코드는 간결하나, 실행 시간은 방법 1)이 3배 빠르다.

def solution(numbers, target):
    # 종료 조건
    # 결과는 좌항, 우항이 같아야 하므로, 좌항을 우항으로 모두 넘겼을 때 target = 0
    if not numbers and target == 0:
        return 1
    elif not numbers:
        return 0
    #배열의 첫 번째 인자가 양수일 때 + 음수일 때
    return solution(numbers[1:], target - numbers[0]) + solution(numbers[1:], target + numbers[0])