프로그래머스 - 타겟 넘버

lv. 2 단계의 코딩 테스트 연습 문제 중 '타겟 넘버'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 타겟 넘버

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 원리라고 할 것이 없을 정도로 간단하다.
• 각 숫자 앞에 + 혹은 - 연산자를 두고 다 계산했을 때, 타겟 넘버가 되는 경우의 수를 구하면 된다.
• 예를 들어, [1, 1, 1, 1, 1] 다섯 개의 숫자가 주어지면, 연산자 역시 다섯 개가 필요하다.
  • 0 {연산자 1} 1 {연산자 2} 1 {연산자 3} 1 {연산자 4} 1 {연산자 5} 1 = N
  • 계산을 쉽게 하기 위해서 앞에 0을 덧붙였다.
• 최대 올 수 있는 숫자의 길이가 20개이기 때문에 연산자도 20개가 필요하다.
• 연산자가 들어갈 자리에는 항상 +, - 연산자, 2 개의 연산자가 들어갈 수 있기 때문에 2^20 = 백만 정도의 경우를 탐색하면 된다.
• 1억이 1초임을 감안하면 충분한 것을 알 수 있다.
• 그래서 DFS 탐색을 이용해서 모든 경우를 구한다.
  • [1, 1, 1]이 주어진다면,,,
  • 0 + 1 + 1 + 1
  • 0 + 1 + 1 - 1
  • ...
  • 0 - 1 - 1 - 1
  • 와 같은 식으로 전부 계산해보면된다.
• 코드는 아래와 같다.
• 재귀함수 형태로 풀었고, 전역 변수를 적절히 활용했다.

코드

def dfs(result, depth):
    global answer, n, t
    if depth == len(n) and result == t:
        answer += 1
    elif depth < len(n):
        for i in range(1, 3):
            result += n[depth]*((-1)**i)
            dfs(result, depth+1)
            result -= n[depth]*((-1)**i)
            
q = []
def solution(numbers, target):
    global answer, n, t
    n = numbers
    t = target
    
    dfs(0, 0)
    return answer

answer = 0
n = []
t = 0

 

롯데 이노베이트 코테를 위해서 알고리즘 고득점 Kit을 앞으로도 열심히 풀어볼 생각이다.

 

추천글

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

프로그래머스