[LeetCode] 322. Coin Change

문제

leetcode.com/problems/coin-change/

Coin Change - LeetCode

 

잠깐만

0부터 코인들을 더해볼까요?

아니면, 목표 값에서 코인들을 하나씩 빼볼까요?

 

코드

22년 2월 17일 코드

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        if amount == 0 {
            return 0
        }
    
        var result = Array(repeating: -1, count: amount + 1)
        result[0] = 0
    
        for index in 1...amount {
            var minCoins = -1
        
            coins.forEach { coin in
                let beforeIndex = index - coin
                if beforeIndex >= 0, result[beforeIndex] >= 0 {
                    var tempResult = result[beforeIndex] + 1
                
                    if minCoins == -1 {
                        minCoins = tempResult
                    } else {
                        minCoins = min(minCoins, tempResult)
                    }
                }
            }
        
            if minCoins > -1 {
                result[index] = minCoins
            }
        }
        return result[amount]
    }
}

 

설명

현재 index에서 가지고 있는 코인들을 뺀 이전 index의 값들로부터 최소값을 가져와  저장하며 나아갑니다.

예를들어, 코인인 목록이 [1, 2, 5]이며, 현재 6원이라고 생각해봐요.

그럼 6원을 어떻게 만들어요??

1원에서 5코인을 더할수 있고

4원에서 2코인을 더할수 있고

5원에서 1코인을 더하여 6원을 만들수 있습니다. 그쵸???

 

그럼 7원은 어떻게 만들어요?

2원에서 5코인을 더할 수 있고

5원에서 2코인을 더할 수 있고

6코인에서 1코인을 더할 수 있습니다.

 

이렇게 하나하나 계산하여 나아가면 됩니다.

그림이 복잡하여, 9원 이후부터는 그리지 않았습니다.

 

 

 

작년에 구현한 코드와 비교하면 성능이 훨씬 좋아졌습니다.

 

---------------------------------------------------------------------------------------------------------------------

코드

21년 4월 15일 코드

class Solution {
    func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        if amount == 0 {
            return 0
        }
        var sortedCoins = coins.sorted()
        var amounts = [Int](repeating: 0, count: amount + 1)
        
        var index = amount
        while index >= 1 {
            if amounts[index] == 0, index != amount {
                index -= 1
                continue
            }
            
            searchCoin: for coin in sortedCoins {
                var nextIndex = index - coin
                if nextIndex < 0 {
                    break searchCoin
                }
                
                var num = amounts[index] + 1
                amounts[nextIndex] = amounts[nextIndex] == 0 ? num : min(amounts[nextIndex], num) 
            }
            index -= 1
        }
        
        return amounts[0] == 0 ? -1 : amounts[0]
    }
}

설명

coinChange([1,2,5], 11) 을 기준으로 설명할게요

목표값인 11부터 코인들(1, 2, 5)을 빼가며, 최소값들을 저장해 나가면 됩니다.

그리고 amounts[목표값]을 제외하고 값이 0이라면, 가능한 루트가 없다는 의미니, continue로 다음 계산을 수행합니다.

또, amount = 0일때 답은 0이기 때문에, 예외사항을 추가했어요

 

혹시 다음 코드 때문에 좀 놀라셨나요?

swift는 for문과 while문 등에 이름을 붙여줄수 있어요.

searchCoin: for coin in sortedCoins {
    var nextIndex = index - coin
    if nextIndex < 0 {
        break searchCoin
    }
            
    var num = amounts[index] + 1
    amounts[nextIndex] = amounts[nextIndex] == 0 ? num : min(amounts[nextIndex], num) 
}

입력받은 coins들을 오름차순으로 정렬하고,

"searchCoin"이라는 이름을 붙여줬고, 다음 값이 0보다 작을때(불가능 할 때) break해줬습니다.

오름 차순이기 때문에 다음 코인일때의 "index - coin" 또한 0보다 작겠죠?

근소하게나마 속도를 향상할 수 있었어요.

 

회고

이전에 풀어본 문제를 다시 풀어보니, 느끼는게 많습니다.

같은 로직으로 접근하는 문제들도 있었고,

다른 로직으로 구현하는 문제들도 있었습니다.

또, 이전 코드를 보며 스스로의 문제점을 찾을 수 있었고, 셀프 코딩리뷰를 할 수 있었어요.

조금이나마 성장한 부분도 느껴집니다.

여러분 같이 화이팅 해요