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

문제

프로그래머스 타겟 넘버

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

프로그래머스

 

코드

answer = 0

def dfs(numbers, target, result, idx):
    global answer

    # 종료조건
    if idx == len(numbers):
        if result == target:
            answer += 1
            return
        else:
            return

    # 더했을때
    dfs(numbers, target, result + numbers[idx], idx + 1)
    # 뺏을때
    dfs(numbers, target, result - numbers[idx], idx + 1)


def solution(numbers, target):
    global answer
    dfs(numbers, target, 0, 0)
    return answer

 

풀이

요약

DFS를 이용해 풀었다.

해당 숫자를 연산 할때마다 idx += 1 해서 idx가 숫자의 총 개수와 같아지면 연산 결과와 타겟 번호가 같은지 판단하여 타겟 번호와 같다면 정담 += 1 하도록 한다.

 

def dfs(numbers, target,result, idx):

 

number는 문제에서 주어지는 숫자배열

target은 number 배열의 숫자들을 더하고 빼서 만들어야하는 목표 숫자

result는 numbers 배열의 숫자들을 더하고 빼서 만든 모든 경우의 결과 숫자

idx는 깊이를 나타낸다. 숫자를 더하고 빼는 작업을 할때마다 idx += 1 하여 깊이를 1씩 늘려간다.

 

global answer

answer는 함수 외부에 있는 변수이기때문에 함수 안에서 쓸려면 global 선언을 해주어 전역 변수로 사용해야한다.

 

• 지역 변수 : 함수가 끝날때 함수 내부에서 선언했던 변수도 같이 사라진다. 이런 변수를 지역변수 라고 한다.
• 전역 변수 : 함수 가 끝날때도 사라지지 않는 변수가 있다. 이를 전역 변수라고 한다. 하지만 전역변수는 프로그램이 복잡해질수록 골칫거리가 되는 경우가 많기 때문에 지역변수와 전역변수를 적절히 사용해야한다.

 

# 종료조건
if idx == len(numbers):
    if result == target:
        answer += 1
        return
    else:
        return

깊이(idx)가 숫자의 총 개수와 같아진다면, 결과 숫자가 타겟숫자와 같은지 비교한다.

결과숫자와 타겟숫자가 같다면 answer += 1 후 지금 깊이보다 -1 한 곳으로 return 한다.

결과숫자와 타겟숫자가 같지 않다면 아무작업 없이 지금 깊이보다 -1 한 곳으로 return 한다.

 

# 더했을때
dfs(numbers,target, result + numbers[idx], idx + 1)

더하기 연산을 했을때 해당 숫자(number[idx])를 지금 결과숫자에 더하고 깊이(idx)를 1 더한다.

 

# 뺏을때
dfs(numbers, target, result - numbers[idx], idx + 1)

빼기 연산을 했을때 해당 숫자(number[idx])를 지금 결과숫자에 빼고 깊이(idx)를 1 더한다.

 

해당문제 dfs()의 작동방식

 

def solution(numbers, target):
    dfs(numbers, target, 0, 0)
    return answer

solution()에서 dfs()를 통해 구한 answer을 반환한다.

 

다른코드

answer = 0
def solution(numbers, target):

    def dfs(result, idx):
        global answer

        if idx == len(numbers):
            if result == target:
                answer += 1
                return
            else:
                return

        # 더했을때
        dfs(result + numbers[idx], idx + 1)

        # 뺏을때
        dfs(result - numbers[idx], idx + 1)

    dfs(0, 0)
    return answer

같은 팀 스터디원의 코드를 참고하여 내 코드를 바꿔보았다.

 

풀이

dfs()를 solution()함수 안에 넣었다.

dfs 작동 방식은 전과 동일하다.

dfs()를 solution()함수 안에 넣으니 dfs()에 쓰일 매개 변수가 적어지고, 코드 실행속도가 빨라졌다.

코드의 실행속도가 빨라진 이유는 세가지다.

1. 함수 매개변수 감소 : 매개 변수가 줄어들면 함수 호출시 전달해야하는 데이터양이 적어진다.
2. 내부 함수 사용 : 함수가 필요한 함수를 전역 스코프가 아닌 로컬 스코프에서 직접 참조 할 수 있기 때문에 전역변수를 사용할때보다 접근이 편리해진다. 
3. 전역 변수 접근 감소 : 전역변수 answer에 접근하는 횟수가 줄어들어 오버헤드가 감소한다.

 

스터디원의 코드는 answer를 전역변수 처리가 아닌 주소형태로 바꾸어 접근하는 방식이다.

 

함수와 함수(처음 코드)
테스트 1 〉	통과 (571.88ms, 10.1MB)
테스트 2 〉	통과 (584.73ms, 10.2MB)
테스트 3 〉	통과 (0.66ms, 10.4MB)
테스트 4 〉	통과 (1.40ms, 10.2MB)
테스트 5 〉	통과 (15.73ms, 9.98MB)
테스트 6 〉	통과 (1.13ms, 10.3MB)
테스트 7 〉	통과 (0.38ms, 10.1MB)
테스트 8 〉	통과 (5.52ms, 10.2MB)

함수속 함수(스터디원 코드 참고)
테스트 1 〉	통과 (370.24ms, 10.2MB)
테스트 2 〉	통과 (391.46ms, 10.1MB)
테스트 3 〉	통과 (0.38ms, 10.3MB)
테스트 4 〉	통과 (1.61ms, 10.2MB)
테스트 5 〉	통과 (14.57ms, 10MB)
테스트 6 〉	통과 (1.08ms, 10.3MB)
테스트 7 〉	통과 (0.36ms, 10.3MB)
테스트 8 〉	통과 (2.98ms, 10.2MB)

 

새롭게 배운점/느낀점

• 내부함수로 바꾸면 실행속도가 빨라진다는것을 알게 되었다. 그리고 어떤 요인들이 실행속도를 빠르게 만드는지도 알게 되었다.
• 전역변수 처리 대신 리스트로 주소형태로 접근할 수 있다는것을 알게 되었다.

 

더 나은 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)