[Day5] [코딩테스트연습] 사탕담기

[코딩테스트연습] 사탕담기

문제 설명

m 그램(gram)을 담을 수 있는 가방에 사탕을 가득 채우는 경우의 수를 구하려 합니다. 단, 같은 사탕은 또 넣을 수 없습니다.

가방이 감당할 수 있는 무게 m, 사탕별 무게가 담긴 배열 weights가 매개변수로 주어질 때, 가방을 정확히 m 그램으로 채우는 경우의 수를 return 하는 solution 함수를 작성해주세요.

제한 조건

• m은 1,000 이상 100,000 이하인 자연수입니다.
• 모든 사탕의 무게는 10 이상 100,000 이하인 자연수입니다.
• weights의 길이는 3 이상 15 이하입니다.

입출력 예

m	weights	return
3000	[500, 1500, 2500, 1000, 2000]	3

입출력 예 설명

사탕을 하나씩 선택해 3000 그램으로 만드는 방법은 [500, 1000, 1500], [1000, 2000], [500, 2500] 으로 3가지입니다.

문제 해결

정확히 사탕 무게 만큼만 사탕을 선택해야 하는 문제이다. 이에 해당 되는 해를 여러개 구해 그 해들의 갯수를 출력하면 된다. 예시로 [500, 1000, 1500] 이 선택 되였다면 이를 [1, 1,0,1,0] 이런식으로 해의 인덱스만 담아서 풀이를 해보려고 한다.

이러한 문제의 경우 조합(combination)을 이용 할 수도, DFS(깊이우선탐색) 방식을 사용해서 풀 수 있다.

조합 (Combination) 이용한 풀이

사탕 무게의 조합을 모두 구해 문제를 해결한다. 조합 풀이를 위해 itertools 라이브러리의 combinations 메소드를 사용한다.

코드 구현

from itertools import combinations

def solution(m, weights):
    answer = 0
    for i in range(1, len(weights)):
        sols = combinations(weights, i)
        for sol in sols:
            if sum(sol) == m:
                answer += 1
    return answer

사탕 무게에서 1개를 뽑았을 때, 2개를 뽑았을때 ,... , 의 경우를 해집합(sols) 으로 만든다음 각 해집합이 가능하면 answer 의 갯수를 +1 한다.

더 Pythonic 한 구현

count() 메소드와 리스트 컴프리헨션을 사용한 풀이

# 더 깔끔한 풀이
from itertools import combinations

def solution(m, weights):
    answer = 0
    for i in range(1, len(weights)):
        answer += [sum(sol) for sol in combinations(weights, i)].count(m)
    return answer

DFS(깊이우선탐색)을 사용한 풀이

해집합

해집합 리스트를 생성하여 탐색이 가능하면 1로 해 가능여부를 표시하고 불가능 하다면 0 을 표시하여 해집합을 구성한다.

종료 조건

재귀적 방식을 사용해서 DFS를 구현하기 때문에 종료조건을 명시 해야한다. 해집합이 가능 할때 answer 를 +1 하고 함수를 종료한다. 또한, 해집합의 사탕의 무게가 이미 m 을 초과 하게 되면 다음 해집합이 유망하지 않다고 판단하여 함수를 종료한다.

코드 구현

def dfs(x, i, weights,m):
    global answer
    total = sum([x*y for x,y in zip(weights, x)])
    # 종료 조건
    if  total == m:
        answer += 1
        return
    # 사탕 무게를 넘아가는 경우 더 이상 탐색을 하지 않는다.
    if i >= len(weights) or total > m:
        return
	# 해집합의 인덱스(i)를 한개씩 늘려가며 탐색
    for j in range(i, len(weights)):
        x[j] = 1
        dfs(x, j+1, weights,m)
        x[j] = 0

answer = 0
def solution(m, weights):
    global x, answer
    x = [0] * len(weights)
    dfs(x, 0, weights,m)
    return answer

코드 구현 - 클로저

프로그래머스 채점 프로그램상 solution 함수에 코드를 작성해야한다. 이때 외부에서 함수를 사용 해야 할 때, 전역변수로 값을 전달 해 줄 수 없어 solution 에서 선언한 변수를 호출 하고자 하는 함수에 인자로 전달 해야한다. dfs(x, i, weights,m). 이를 간단히 해결해주는 방식이 클로저 기법중 nonlocal 을 사용하는 방법이다.

def solution(m, weights):
    # solution 함수 내에서 dfs 함수 선언
    def dfs(x, i):
        # nonlocal 선언
        nonlocal answer
        total = sum([x*y for x,y in zip(weights, x)])
        # 종료 조건
        if  total == m:
            answer += 1
            return
        # 사탕 무게를 넘아가는 경우 더 이상 탐색을 하지 않는다.
        if i >= len(weights) or total > m:
            return

        for j in range(i, len(weights)):
            x[j] = 1
            dfs(x, j+1)
            x[j] = 0
    
    x = [0] * len(weights)
    dfs(x, 0)
    return answer

위와 같이 클로저 형태로 solution 함수 안에 함수를 선언 해서 사용할 수 있다. 단, 이때 nonlocal로 지역 변수를 지정 해줘야 한다.

보충 설명

클로저 - nonlocal

지금까지 바깥쪽 함수의 지역 변수를 안쪽 함수에서 사용해왔다. 그럼 바깥쪽 함수의 지역 변수를 안쪽 함수에서 변경하면 어떻게 될까?

def A():
    x = 10        # A의 지역 변수 x
    def B():
        x = 20    # x에 20 할당
 
	B()
    print(x)      # A의 지역 변수 x 출력
 
A()

10

실행을 해보면 20이 나와야 할 것 같은데 10이 나왔다. 안쪽 함수 B에서 이름이 같은 지역 변수 x를 새로 만들게 된다. 즉, 파이썬에서는 함수에서 변수를 만들면 항상 현재 함수의 지역 변수가 된다.

현재 함수의 바깥쪽에 있는 지역 변수의 값을 변경하려면 nonlocal 키워드를 사용해야 한다. 다음과 같이 함수 안에서 nonlocal에 지역 변수의 이름을 지정해줍니다.

def A():
    x = 10        # A의 지역 변수 x
    def B():
        nonlocal x    # 현재 함수의 바깥쪽에 있는 지역 변수 사용
        x = 20        # A의 지역 변수 x에 20 할당
 
    B()
    print(x)      # A의 지역 변수 x 출력
 
A()

20

global 로 전역변수 사용하기

특히, 함수가 몇 단계든 상관없이 global 키워드를 사용하면 무조건 전역 변수를 사용하면 된다.

x = 1
def A():
    x = 10
    def B():
        x = 20
        def C():
            global x
            x = x + 30
            print(x)
        C()
    B()
 
A()

31