리트코드 - 322. Coin Change

리트코드 - 322. Coin Change

출처 - https://leetcode.com/problems/coin-change/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 배열 coins는 서로 다른 액면가를 나타내는 동전들이며, 정수 amount는 총 금액을 나타냅니다.

이 금액을 만들기 위해 필요한 동전의 최소 개수를 반환하세요. 만약 주어진 동전들의 조합으로 해당 금액을 만들 수 없다면 -1을 반환하세요.

각 동전의 수량이 무한하다고 가정할 수 있습니다.

 

의사코드

n = coins배열의 길이 dp = new int[amount + 1] Arrays.fill(dp, Integer.MAX_VALUE) dp[0] = 0 반복문 시작 (coins 배열 순회)     반복문 시작         if (dp[i - coin] != Integer.MAX_VALUE)             dp[i] = Math.min(dp[i], dp[i - coin] + 1)     반복문 종료 반복문 종료 if (dp[amount] == Integer.MAX_VALUE)     -1 리턴 dp[amount] 리턴

 

풀이코드

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[amount];
    }
}

코드설명

구하고자 하는 수를 단순히 큰 수부터 나누게 되면 최소값을 찾지 못한다.

따라서 그리디로는 풀기 어렵고, DP를 이용하여 최소 동전개수를 찾는 풀이이다.

 

예를 들어 coins = [1, 3, 4 ,5] 이라 수가 주어지고 amount = 7 을 구해야 한다고 하자.

큰 수부터 나누게 되면 7 - 5 = 2 이므로 나머지는 1인 동전 2개를 사용해서 값을 구할 수 있다.

총 5인 동전 1개, 1인 동전 2개로 3개인데 실제로 최소값은 3인 동전 1개 + 4인 동전 1개 = 총 2개 이므로 틀린 답이다.

 

각각의 코인으로 해당 수까지 도달할 수 있는 경우의 수를 구하여 이 값이 최소값인지 확인하여 갱신하면 된다.

 

먼저 dp배열을 만들어 배열의 크기를 amount 보다 하나 크게 만들어주고 모든 배열을 임의의 최댓값으로 채운다.

여기서 임의의 최댓값은(M)으로 두겠다.

그리고 0번째 배열 값을 0으로 만든다.

 

이제 coins 배열을 순회하면서 최소값을 구한다.

먼저 coin 1부터 시작한다.

dp[1]은 1까지 도달할 수 있는 경우의 수이다.

1은 0에서 0+1해서 도달할 수 있는 수이니 0을 확인했는데 임의의 최댓값(M)이 아니다.

따라서 갱신 가능하다.

마찬가지로 dp[2]는 2까지 도달할 수 있는 경우의 수고,

1+1 에서 도달할 수 있고 1이 M이 아니므로 갱신 가능하다.

3의 경우도 이전 값을 확인하고, M이 아니면 갱신하면 된다.

이렇게 1로 amount까지 전부 순회하면 7이된다.

 

다음으로 coin 3이다.

3은 한번에 3을 도달할 수 있고, 0을 확인하니 M이 아니다.

그래서 dp[3]을 봤는데 이미 3이다. 1개로 갱신 가능하므로 1로 바꾸어준다.

다음으로 6이 아니라 4를 확인한다. 배열을 확인할 때는 coin부터 amount까지 모두 확인해야 한다.

4-3을 하여 이 값이 M인지 확인한다. 1이 M이 아니므로 갱신 가능하다.

하지만 이미 dp[4]는 4라는 값을 가지고 있다. dp[1] + 1 과, dp[4]를 비교하여 작은 값을 갱신해준다.

이런식으로 끝까지 순회하면 이런 결과를 얻을 수 있다.

 

여기까지 로직에서 핵심은 이것이다.

1. 현재 값에서 동전만큼 뺀 값이 도달가능한 값인가?(= M을 가지고 있지 않은가?)

2. 도달 가능하다면 이 값이 최소값인가?(= 기존 값과 이전 도달 값+1 중 어떤게 더 작은가?)

 

이런식으로 쭉 진행하면 coin 4를 순회하면 이렇게 될 것이고

최종적으로 dp배열은 이렇게 된다.

 

구현코드

for (int coin : coins) {
    for (int i = coin; i <= amount; i++) {
        if (dp[i - coin] != Integer.MAX_VALUE) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
}

이를 구현한 코드가 이것이다.

dp[amount]를 리턴하게 되면 최소값을 얻을 수있고, 만약 M을 가지고 있다면 -1을 리턴하면 된다.

 

시간복잡도 - O(n * m)

공간복잡도 - O(m) 

 

문제를 풀며 생각한 흐름과 배운 점

반드시 dp배열을 -1로 초기화 할 필요는 없다.

구하고자 하는 값에 따라 유연하게 적용하면 된다.

 

다른코드(DFS)

class Solution {
    public int coinChange(int[] coins, int amount) {
        Map<Integer,Integer> map = new HashMap<>();
        return coinChange(coins, amount, map);
    }

    public int coinChange(int[] coins, int amount, Map<Integer,Integer> mem) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        Integer c = mem.get(amount);
        if (c != null) {
            return c;
        }
        int cc = -1;

        for (int coin : coins) {
            int coinSum = coinChange(coins, amount - coin, mem);
            if (coinSum >= 0) {
                if (cc < 0) {
                    cc = coinSum + 1;
                } else {
                    cc = Math.min(cc, coinSum + 1);
                }
            }
        }
        mem.put(amount, cc);
        return cc;
    }
}

for 문 안에 있는 int coinSum = coinChange(coins, amount - coin, mem); 에서 한 코인에 대해서 재귀적으로 전부 순회하고 있다. 그리고 그 순회한 값을 mem이라는 Map에 저장하고 있다.

 

런타임은 100ms 가 넘지만 이렇게 재귀를 적절하게 활용할 수 있도록 봐둬야겠다.

 

다른코드(BFS)

class Solution {
    public int coinChange(int[] coins, int amount) {
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        int cs = 0;
        boolean[] vstd = new boolean[amount + 1];
        while (!q.isEmpty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                int sum = q.poll();
                if (sum == amount) {
                    return cs;
                }
                if (sum > amount || vstd[sum]) {
                    continue;
                }
                vstd[sum] = true;
                for (int coin : coins) {
                    q.add(sum + coin);
                }
            }
            cs++;
        }
        return -1;
    }
}

Queue를 이용해서 풀수 있을 줄 몰랐다.

그렇지만 위 코드는 정말 모든 경우의 수를 다 훑어서 queue에 넣고 있어 비효율적이다.

 

BFS 리팩토링

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        boolean[] visited = new boolean[amount + 1];
        visited[0] = true;
        int coinChangeCount = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int currentSum = queue.poll();

                for (int coin : coins) {
                    int nextSum = currentSum + coin;

                    if (nextSum == amount) {
                        return coinChangeCount + 1;
                    }

                    if (nextSum < amount && !visited[nextSum]) {
                        queue.add(nextSum);
                        visited[nextSum] = true;
                    }
                }
            }

            coinChangeCount++;
        }

        return -1;
    }
}

큐에서 값을 꺼내, 그값을 더해서 비교하는 로직으로 변경하였더니, 108ms -> 22ms 로 런타임이 줄었다.

BFS는 몇 번 풀어봤지만 이것도 아직 익숙하진 않은 것 같다.

 

정리

동전을 조합하여 특정 수를 만들 수 있는 최소값을 구하는 여러가지 방법(DP, DFS, BFS)