<aside> 💬 lv0, 그리디

최소 동전 개수 찾기

문제 설명

다양한 가치의 동전들이 주어질 때, 특정 금액을 만드는 데 필요한 최소한의 동전 개수를 찾는 함수를 작성해주세요. 각 동전은 무한정 사용할 수 있다고 가정합니다.

예를 들어, 동전의 가치가 [1, 5, 10]이고, 만들어야 할 금액이 18이라면, 최소 동전 개수는 4개입니다 (10, 5, 1, 1).

제한 사항

동전의 종류 수는 1 이상 10 이하입니다.
각 동전의 가치는 1 이상 100 이하의 정수입니다.
만들어야 하는 금액은 1 이상 10,000 이하의 정수입니다.

입출력 예

입력 (동전 가치, 금액)	출력 (최소 동전 개수)
[1, 5, 10], 18	5
[1, 3, 4], 6	3
[1], 100	100

입출력 설명

주어진 동전들을 사용하여 특정 금액을 만드는 데 필요한 최소한의 동전 개수를 계산합니다. 18을 만드는 것에는 10과 5, 1, 1, 1이 필요해서 18금액을 맞추기 위해서는 5개의 동전이 필요합니다.

</aside>

풀이 1. 큰 금액으로 정렬

def solution(data):
    coins = sorted(data['coins'], reverse=True) **#1 동전 정렬, 목표 금액 설정**
    amount = data['amount']
    num_coin = 0

    for coin in coins: **#2 동전 순회 및 계산**
        while amount >= coin:
            amount -= coin
            num_coin += 1
    return num_coin

단계별 풀이 전략

동전 정렬, 목표 금액 설정

(data['coins'], reverse=True)를 통해, 입력으로 받은 동전 종류를 내림차순으로 정렬합니다. amount = data['amount']을 통해 함수에 전달된 목표 금액을 설정합니다.

num_coin 변수를 0으로 초기화하고, 이 변수는 사용된 동전의 총 개수를 카운트 합니다.
동전 순회 및 계산
1. for coin in coins 가장 큰 동전부터 시작하여 각 동전을 순회합니다.
2. while amount >= coin 목표 금액이 현재 동전의 값보다 크거나 같을 때까지 반복합니다.
3. amount -= coin목표 금액에서 현재 동전의 값을 뺍니다.
4. num_coin += 1동전 개수를 하나 증가 시킵니다.
5. 루프에서 현재 동전의 값이 목표 금액보다 작거나 같은 동안 동전을 사용하여 금액을 만듭니다. 이 과정에서 목표 금액을 줄이고, 사용된 동전의 개수를 증가 시킵니다.

알아둬야 할 개념

이 풀이 방법의 핵심은 sorted(data[0], reverse=True) 입니다.

가장 큰 단위 동전부터 사용하여 금액을 만드는 것이 최소 개수의 동전을 사용하는 방법이기 때문입니다. sorted 함수는 원본 데이터를 변경하지 않고, 정렬된 새로운 리스트를 생성하여 반환합니다.

기본 사용법은 아래와 같습니다.

sorted(iterable, *, key=None, reverse=False)

iterable: 정렬할 데이터(리스트, 튜플, 문자열 등 반복 가능한 객체).

key: 정렬 기준을 지정하는데 사용되는 함수. 각 요소에 대해 비교에 사용될 키를 생성합니다.

reverse: 정렬 순서를 결정합니다. False(기본 값)이면 오름차순, **True**면 내림차순 정렬합니다.

사용 예시

fruits = [("apple", 2), ("banana", 4), ("cherry", 1)]
print(sorted(fruits, key=lambda x: x[1]))
# 출력: [('cherry', 1), ('apple', 2), ('banana', 4)]

여기서 key 함수는 각 요소의 두 번째 항목(즉, 숫자)을 정렬 기준으로 사용합니다.

reverse=True 를 뒤에 사용했다면 [('banana', 4), ('apple', 2), ('cherry', 1)] 로 출력 됩니다. 문자열도 사용 가능합니다.