[LeetCode] 322. Coin Change / JAVA

>> 문제설명

leetcode.com/problems/coin-change/

Coin Change - LeetCode

가장 적은 갯수의 동전으로 만들수 있는 수를 늘려가며 목표치만큼의 금액을 만드는 가장 적은 갯수의 동전을 반환하는 동적 계획법 문제다.

저조한 성적의 Distribution Chart를 보고 Hash맵을 Array로 바꿔서 풀어 조금은 나아진 성적표를 받았다.

 

> Solution 1 (Hash Map & DP)

import java.util.HashMap;
import java.util.LinkedList;

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        LinkedList<Integer> nextList = new LinkedList<>();

        hashMap.put(0,0);
        nextList.add(0);

        while (!nextList.isEmpty()){
            int val = nextList.poll();
            for(int coin : coins){
                if(val+coin == amount) return hashMap.get(val)+1;
                if(val+coin > amount || hashMap.containsKey(val+coin)) continue;
                if(hashMap.containsKey(val)){
                    hashMap.put(val+coin, hashMap.get(val)+1);
                    nextList.addLast(val+coin);
                }
            }
        }
        return -1;
    }
}

> Result 1

> Solution 2 (Array & DP)

import java.util.Arrays;

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;

        int[] amountMap = new int[amount+1];
        Arrays.fill(amountMap, Integer.MAX_VALUE);

        amountMap[0] = 0;

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

        return amountMap[amount] == Integer.MAX_VALUE ? -1 : amountMap[amount];
    }
}

> Result 2