[리트코드] Medium 322. Coin Change - 자바(JAVA)

문제 설명

당신에게는 서로 다른 금액 단위를 나타내는 정수 배열 coins와, 총금액을 나타내는 정수 amount가 주어집니다.

 

amount를 만들기 위해 필요한 가장 적은 수의 동전 개수를 반환하세요. 만약 동전의 조합으로 해당 금액을 만들 수 없다면 -1을 반환하세요.

 

각 동전은 무한히 많이 가지고 있다고 가정할 수 있습니다.

 

제한사항

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

---

문제 파악

주어진 동전 종류를 사용해 특정 금액을 만들 때, 필요한 최소 동전 개수를 구하는 문제이다.

 

접근 방법

• bfs를 사용한다.
• 노드는 현재까지 만든 금액을 의미한다.
• 큐에 현재까지 만든 금액을 넣는다.
• 큐에 있는 값(현재 금액)에 동전을 합해서 다음 노드(새로운 금액)를 만든다.
• 이 노드를 전에 방문하지 않았다면 큐에 넣는다.
• amount(목표 금액)에 해당하는 금액이 나오면, 그 노드까지의 거리를 구한다.

 

코드 구현

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0; // 금액이 0이면 동전 개수는 0
        
        //BFS
        Queue<Integer> queue = new LinkedList<>();
        int[] distance = new int[amount + 1];
        Arrays.fill(distance, -1); 

        queue.add(0);
        distance[0] = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            //동전 한 번씩 사용해서 새로운 금액 계산            
            for (int coin : coins) {
                int next = current + coin;

                //금액이 amount를 초과하지 않으면 실행
                if (next <= amount && next >= 0  && distance[next] == -1) {
                    distance[next] = distance[current] + 1; 
                    queue.add(next);
                }
            }
        }

        //목표 금액 만들 수 없으면 -1 반환
        return distance[amount] == -1 ? -1 : distance[amount];
    }
}

• 0부터 시작해서, 동전들을 하나씩 더해가며 목표 금액에 도달한다.
• distance[i]는 i 금액을 만들기 위한 최소 동전 개수이다.
• 목표 금액에 도달할 수 없으면 -1을 반환한다.

 

다른 풀이 (정답 코드)

1) 남은 금액 줄여가기

import java.util.*;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        
        // 방문 저장
        boolean[] visited = new boolean[amount + 1];
        Queue<int[]> queue = new LinkedList<>();
        
        //큐에 초기 상태 추가
        queue.offer(new int[]{amount, 0});
        visited[amount] = true;

        while (!queue.isEmpty()) {
        // 큐에서 남은 금액, 동전 사용 개수 꺼냄
            int[] current = queue.poll();
            int remaining = current[0];
            int numCoins = current[1];
            
            //남은 금액이 0이면, 동전 사용 개수 반환
            if (remaining == 0) {
                return numCoins;
            }
            
            //동전 탐색
            for (int coin : coins) {
                int next = remaining - coin; //동전 사용 후 남은 금액
                
                //남은 금액이 있고, 아직 방문하지 않았으면 큐에 추가
                if (next >= 0 && !visited[next]) {
                    queue.offer(new int[]{next, numCoins + 1});
                    visited[next] = true;
                }
            }
        }
        // 목표 금액 만들 수 없으면 -1 반환
        return -1;
    }
}

• 현재 남은 금액을 감소시키는 방향으로 탐색한다.
• 남은 금액이 0이 되면 동전 개수를 반환한다.

 

2) 클래스 만들기

class Solution {
    public int coinChange(int[] coins, int amount) {
    //✅ amount가 0이면, 0을 반환한다. (예외 처리)
        if (amount == 0) return 0;

        Queue<Entry> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[amount + 1];
        //✅ 초기 금액을 amount, 동전 개수를 0으로 설정하고, 큐에 추가한다.
        queue.add(new Entry(amount, 0));
        //✅ 큐가 빌 때까지 반복문을 수행한다.
        while (!queue.isEmpty()) {
        //✅ 큐에서 현재 남은 금액과 현재 동전 개수를 remove한다.
            Entry cur = queue.remove();
            //✅ 한 동전을 사용해서 다음 남은 금액을 만든다.
            for (int i = 0; i < coins.length; i++) {	
                int nextAmount = cur.amount - coins[i];
                //✅ 다음 남은 금액이 0이면, 현재 동전 개수에 1을 더해서 반환한다.
                if (nextAmount == 0) {
                    return cur.count + 1;
                    //✅ 다음 남은 금액이 0보다 크고, 다음 남은 금액이 처음 발생하면,
                } else if (nextAmount > 0 && !visited[nextAmount]) {
                //✅ 다음 남은 금액과 동전 개수에 1을 더해서 큐에 추가한다.
                    queue.add(new Entry(nextAmount, cur.count + 1));
                    //✅ visited에서 다음 남은 금액에 대해 true로 처리한다.
                    visited[nextAmount] = true;
                }
            }
        }
        //✅ coins의 동전으로 amount를 만들 수 없다면 -1을 반환한다.
        return -1;
    }

    static class Entry {
        int amount;
        int count;

        public Entry(int amount, int count) {
            this.amount = amount;
            this.count = count;
        }
    }
}

• Entry 클래스를 만들어 금액과 동전 개수를 같이 관리해서 더 편리하다.

 

3) Set 사용

import java.util.*;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        Queue<int[]> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        // ✅ 초기 상태 추가: (남은 금액, 사용한 동전 수)
        queue.offer(new int[]{amount, 0});
        visited.add(amount);

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int remaining = current[0];
            int numCoins = current[1];

            // ✅ 금액을 정확히 맞췄을 경우
            if (remaining == 0) {
                return numCoins;
            }

            // ✅ 가능한 동전으로 다음 상태 탐색
            for (int coin : coins) {
                int next = remaining - coin;
                if (next >= 0 && !visited.contains(next)) {
                    queue.offer(new int[]{next, numCoins + 1});
                    visited.add(next);
                }
            }
        }

        // ✅ 만들 수 없는 경우
        return -1;
    }
}

• HashSet을 사용해서 더 빠른 속도로 탐색 가능하다.

 

배운 점

• 최소 횟수를 구하는 문제에서 BFS가 유용하다.
• 이미 방문한 노드인지 확인이 꼭 필요하다.