[Java Algorithm] 거스름돈 문제 풀이 예시 따라가보기

Self Check : 

기본 코드에 대한 이해도 O / 시간 복잡도 분석 보완 필요

---

🙋‍♂️ 문제 분석

철수는 물건을 구매하고 거스름돈을 받아야 합니다. 가게에는 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정할 때, 특정 금액을 거슬러주기 위한 최소한의 동전 개수를 구하는 프로그램을 작성해보세요.

---

⚠️ 제약사항

• 사용할 수 있는 동전의 종류: 500원, 100원, 50원, 10원

---

💬 입력 방식

// 입력 예시 1
1260

// 입력 예시 2
830

• 첫째 줄에 거슬러 주어야 할 금액 N이 주어집니다. (0 ≤ N ≤ 10,000)

---

🖨️ 출력 방식

// 출력 예시 1
6

// 출력 예시 2
7

• 거스름돈 N원을 만들기 위한 최소 동전 개수를 출력합니다.

---

📂 입출력 예시

# 예시 1: 1260원
500원 2개, 100원 2개, 50원 1개, 10원 1개
총 6개의 동전이 필요합니다.

# 예시 2: 830원
500원 1개, 100원 3개, 50원 0개, 10원 3개
총 7개의 동전이 필요합니다.

---

🧐 문제 풀이 접근 방법

1단계 : 문제 이해 및 요구사항 분석하기

문제: N원을 거슬러줄 때 필요한 동전의 최소 개수 구하기
- 목표: 최소한의 동전 개수로 거스름돈 만들기
- 입력: 거스름돈 금액 N원 (0 ≤ N ≤ 10,000)
- 출력: 최소 동전 개수
- 조건: 동전 종류는 500원, 100원, 50원, 10원

 

2단계 : 접근 방법 구상하기

입력 금액 (N원)
  ↓
500원으로 최대한 거슬러주기
  ↓
남은 금액을 100원으로 최대한 거슬러주기
  ↓
남은 금액을 50원으로 최대한 거슬러주기
  ↓
남은 금액을 10원으로 최대한 거슬러주기
  ↓
사용된 동전 개수 합산

 

3단계 : 세부 구현 설계 및 검토하기

풀이:
1. 초기화 단계
   1.1. 동전을 큰 단위부터 작은 단위 순으로 정렬
   1.2. 거스름돈 금액을 저장할 변수 초기화
   1.3. 사용된 동전 개수를 저장할 변수 초기화

2. 거스름돈 계산 단계
   2.1. 가장 큰 단위의 동전부터 순차적으로 진행
   2.2. 현재 동전으로 거스름돈을 최대한 많이 거슬러줌
   2.3. 남은 거스름돈에 대해 다음으로 큰 동전으로 반복

3. 결과 반환 단계
   3.1. 사용된 동전 개수 반환

시간복잡도 분석:
1. 초기화 단계: O(1)
2. 거스름돈 계산 단계: O(K) - K은 동전의 종류 수
3. 결과 반환 단계: O(1)
→ 최종 시간복잡도: O(K)

 

4단계 : 코드 작성 및 구현하기

 

5단계 : 테스트와 디버깅

---

👍 세부 아이디어

---

👨🏻‍💻 나의 코드

package example;
import java.util.*;

public class Solution {
    public static int coinChange(int[] coins, int target) {
        // 1. 초기화 단계
        // 1.1. 동전을 큰 단위부터 작은 단위 순으로 정렬
        Arrays.sort(coins);

        // 1.2. 거스름돈 금액을 저장할 변수 초기화
        int remainingAmount = target;
        // 1.3. 사용된 동전 개수를 저장할 변수 초기화
        int coinCount = 0;

        // 2. 큰 동전부터 사용하는 단계
        // 2.1. 가장 큰 단위의 동전부터 순차적으로 진행
        for (int i=coins.length-1; i>=0; i--){
            // 2.2. 현재 동전으로 거스름돈을 최대한 많이 거슬러줌
            coinCount += remainingAmount / coins[i];  // 현재 동전으로 거슬러 줄 수 있는 개수
            remainingAmount %= coins[i];              // 남은 금액 계산
            // 2.3. 남은 거스름돈에 대해 다음으로 큰 동전으로 반복
        }

        // 3. 결과 반환 단계
        // 3.1. 사용된 동전 개수 반환
        return coinCount;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] coins = {500, 100, 50, 10};

        // 거스름돈 금액 입력 받기
        int target = scanner.nextInt();

        // 결과 출력
        System.out.println(coinChange(coins, target));
    }
}

---

📈  시간 복잡도 분석

#Check running complication

Arrays.sort(coins);        // 정렬 → O(n log n)
for (...) { ... }          // 단순 반복 → O(n)

👉 합치면 O(n log n + n)
👉 최종 정리: O(n log n)

---

😲 다른 사람들의 풀이 방법 및 코드 (참고자료 있을 경우)

Other Code#1