LeetCode - 322.Coin Change(BFS)

 

문제 분석

- 주어진 동전으로 특정 금액을 만들 때 필요한 동전의 최소 개수를 구하는 문제

- 최소 횟수로 목표를 달성하는 것 -> 최단 경로 문제로 볼 수 있음

- 동전 무한으로 쓸 수 있음, 같은 동전 여러번 사용 가능

 

현재까지 만든 금액이 변환하는 과정을 추적해야함

각 상태에서 다음 상태는 현재 금액 + 동전의 값

종료 상태는 현재 금액이 amount가 되는 순간

최소 동전 개수를 구하는 것이므로, 목표 상태에 가장 빨리 도달하는 경로를 찾아야함

 

문제 해결 흐름

bfs를 통해 해결해주었음

deque를 통해 초기 동전 갯수와 초기 금액을 설정해주었고,

종료 조건을 통해 deque에 있는 모든 큐가 빠져나갈때동안 coins배열의 있는 동전을 각각 더해주어서 허용이 되는지 안되는지를 판별해주었음.

종료 조건은 현재 금액이 목표 금액과 같을때로 설정 해줌

 while(!deque.isEmpty()) {
            int[] arr = deque.pollFirst();
            int current_coin = arr[0];
            int current_amount = arr[1];

            // 종료조건 설정해줌(현재 금액이 목표 금액과 같다면)
            if (current_amount == amount) {
                return current_coin;
            }

            for (int i=0; i< coins.length; i++) {
                if (current_amount > amount - coins[i]) {
                    continue;
                }
                int new_amount = current_amount + coins[i];
                if (new_amount > amount || visited[new_amount] == true) {
                    continue;
                }
                visited[new_amount] = true;
                deque.addLast(new int[]{current_coin +1, new_amount});
            }
        }

 

트러블 슈팅

for (int i=0; i< coins.length; i++) {
                int new_amount = current_amount + coins[i];
                if (new_amount > amount || visited[new_amount] == true) {
                    continue;
                }
                visited[new_amount] = true;
                deque.addLast(new int[]{current_coin +1, new_amount});
            }

초기에 이렇게 for문을 통해 유효성을 검사해주는 부분 코드에서 에러가남

java.lang.ArrayIndexOutOfBoundsException: Index -2147483648 out of bounds for length 3
  at line 26, Solution.coinChange
  at line 56, __DriverSolution__.__helper__
  at line 89, __Driver__.main

 

에러의 원인을 살펴보니 자바에서 Integer.MIN_VALUE가 coins 배열에 존재하게되어서 int 의 범위를 벗어났을 경우에 에러가 남.

이 부분을 해결해 주기 위해 검사 코드를 하나 추가해서 문제를 해결함

 

 for (int i=0; i< coins.length; i++) {
 				// int범위 유효성 검사 코드
                if (current_amount > amount - coins[i]) {
                    continue;
                }
                int new_amount = current_amount + coins[i];
                if (new_amount > amount || visited[new_amount] == true) {
                    continue;
                }
                visited[new_amount] = true;
                deque.addLast(new int[]{current_coin +1, new_amount});
            }

 

최종적으로 while문 안에서의 종료 조건에 들어간다면 해당 코인 갯수를 반환하게 하였고,

만약 deque에 모든 큐들이 빠질때까지 종료조건에 걸리지 않는다면 -1을 반환하게 해주어서 코드를 작성함.

 

최종 코드

class Solution {
    public int coinChange(int[] coins, int amount) {
        boolean[] visited = new boolean[amount +1];

        Deque<int[]> deque = new ArrayDeque<>();
        // deque 초기에 현재 금액과 현재 사용된 동전 개수 넣어줌
        deque.addLast(new int[]{0,0});

        // 현재 금액 방문 처리
        visited[0] = true;
        while(!deque.isEmpty()) {
            int[] arr = deque.pollFirst();
            int current_coin = arr[0];
            int current_amount = arr[1];

            // 종료조건 설정해줌(현재 금액이 목표 금액과 같다면)
            if (current_amount == amount) {
                return current_coin;
            }

            for (int i=0; i< coins.length; i++) {
                if (current_amount > amount - coins[i]) {
                    continue;
                }
                int new_amount = current_amount + coins[i];
                if (new_amount > amount || visited[new_amount] == true) {
                    continue;
                }
                visited[new_amount] = true;
                deque.addLast(new int[]{current_coin +1, new_amount});
            }
        }

        return -1;
    }
}