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

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

프로그래머스

 

• n개의 음이 아닌 정수들이 있음
• 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 함
• numbers: 사용할 수 있는 숫자가 담긴 배열
• target: 타겟 넘버
• 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하
• 각 숫자는 1 이상 50 이하인 자연수
• 타겟 넘버는 1 이상 1000 이하인 자연수

 

"""
입출력 예시)

numbers = [1, 1, 1, 1, 1], target = 3 -> 5
numbers = [4, 1, 2, 1], target = 4 -> 2
"""

# numbers = [1, 1, 1, 1, 1], target = 3 -> 5

# -1+1+1+1+1 = 3
# +1-1+1+1+1 = 3
# +1+1-1+1+1 = 3
# +1+1+1-1+1 = 3
# +1+1+1+1-1 = 3

# => 5가지

# numbers = [4, 1, 2, 1], target = 4 -> 2

# +4+1-2+1 = 4
# +4-1+2-1 = 4

# => 2

 

 

## 의사코드 ##

# 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼기 -> DFS
# -> stack

# 큐.pop()한 원소가 방문할 수 있는 값: 다음 인덱스에 위치한 numbers의 원소에 + 또는 -한 값

# 큐에 [+정수, 인덱스]와 [-정수, 인덱스] 삽입

# while q:
#     temp, idx = 큐.pop()
#     idx += 1
#     if idx < len(numbers):
#         큐.append([temp+numbers[idx], idx])
#         큐.append([temp-numbers[idx], idx])
#     else:
#         if temp == target:
#             answer += 1

 

 

 

통과한 코드

 

def solution(numbers, target):
    answer = 0
    q = [[numbers[0], 0], [-1*numbers[0], 0]] # [+정수, 인덱스], [-정수, 인덱스]
    while q: 
        temp, idx = q.pop()
        # 다음 인덱스에 위치한 값으로 탐색
        idx += 1
        if idx < len(numbers):
            q.append([temp+numbers[idx], idx])
            q.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

-> stack으로 구현한 DFS 활용

 

 

• 과정 확인

numbers = [4, 1, 2, 1]
target = 4

"""
시작 q: [[4, 0], [-4, 0]] 

temp: -4
idx: 0
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[4, 0], [-3, 1], [-5, 1]] 

temp: -5
idx: 1
다음 인덱스에 위치한 numbers 원소의 + 값: 2
다음 인덱스에 위치한 numbers 원소의 - 값: -2
갱신된 q: [[4, 0], [-3, 1], [-3, 2], [-7, 2]] 

temp: -7
idx: 2
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[4, 0], [-3, 1], [-3, 2], [-6, 3], [-8, 3]] 

temp: -8
idx: 3
temp: -6
idx: 3
temp: -3
idx: 2
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[4, 0], [-3, 1], [-2, 3], [-4, 3]] 

temp: -4
idx: 3
temp: -2
idx: 3
temp: -3
idx: 1
다음 인덱스에 위치한 numbers 원소의 + 값: 2
다음 인덱스에 위치한 numbers 원소의 - 값: -2
갱신된 q: [[4, 0], [-1, 2], [-5, 2]] 

temp: -5
idx: 2
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[4, 0], [-1, 2], [-4, 3], [-6, 3]] 

temp: -6
idx: 3
temp: -4
idx: 3
temp: -1
idx: 2
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[4, 0], [0, 3], [-2, 3]] 

temp: -2
idx: 3
temp: 0
idx: 3
temp: 4
idx: 0
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[5, 1], [3, 1]] 

temp: 3
idx: 1
다음 인덱스에 위치한 numbers 원소의 + 값: 2
다음 인덱스에 위치한 numbers 원소의 - 값: -2
갱신된 q: [[5, 1], [5, 2], [1, 2]] 

temp: 1
idx: 2
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[5, 1], [5, 2], [2, 3], [0, 3]] 

temp: 0
idx: 3
temp: 2
idx: 3
temp: 5
idx: 2
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[5, 1], [6, 3], [4, 3]] 

temp: 4
idx: 3
temp: 6
idx: 3
temp: 5
idx: 1
다음 인덱스에 위치한 numbers 원소의 + 값: 2
다음 인덱스에 위치한 numbers 원소의 - 값: -2
갱신된 q: [[7, 2], [3, 2]] 

temp: 3
idx: 2
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[7, 2], [4, 3], [2, 3]] 

temp: 2
idx: 3
temp: 4
idx: 3
temp: 7
idx: 2
다음 인덱스에 위치한 numbers 원소의 + 값: 1
다음 인덱스에 위치한 numbers 원소의 - 값: -1
갱신된 q: [[8, 3], [6, 3]] 

temp: 6
idx: 3
temp: 8
idx: 3

2
"""

 

 

 

cf) 이전에 작성했던 코드

 

https://monzheld.tistory.com/56

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

 

 

 

참고)

 

https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS

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