★Coin Change(추가질문요청)★

Coin Change - LeetCode

★다시 풀어봐야할 문제★ (해설코드 참고하여 풀었음, 디다음 풀때는 Time Limit, Memory Limit 을 어떻게 통과할 것인지 다시 고민해보기)

접근 방법 [필수 작성]

제한 조건 확인

• Return the fewest number of coins that you need to make up that amount.
• If that amount of money cannot be made up by any combination of the coins, return -1.
• You may assume that you have an infinite number of each kind of coin.

1차 아이디어 흐름

어떤 숫자로 구성할지, 어떤 숫자가 목표 숫자가 될지 알 수 없음

가장 큰 숫자로 빼다보면?

반례:

[1,4,5] , 12

5 5 1 1 vs 4 4 4

가장 큰 숫자부터 빼는걸 완전탐색하면?

완전탐색?

2^10 ~~ 10^3

[1,2] , 10^4

10^8 이내

지금까지 만들 수 있었던 최소 코인 조합 갯수 계속 업데이트

0이 되면 return

최대숫자부터 순차적으로 빼다가 안되면 -1 리턴

반례:

근데 amount 가 최대코인보다 더 많이 남아도 미리 중단해야하는 경우가 있는가? → 있음

[1,4,5] , 17

5 5 5 1 1

4 4 4 4 1

1 1 1 ~~~

5 4 4 4

그럼 완전탐색을 큰수에서 무조건 작아질때까지 빼는게 아니라

큰수에서 뺄수 있을때, 1개만 빼보고 그 이후는 가능한 모든 경우를 백트래킹으로 완전탐색 구현해야됨

만약 min_coin_num보다 커지면 더 탐색할 필요가 없어짐

2차 아이디어 흐름

위에서 부터 쓸고 내려오는건 안된다.

그리디도 안되고, 완전탐색도 안된다.

그럼 아래서부터 쓸면서 올라가야하나?

아래에서부터 합쳐서 더 큰 숫자를 만들 수 있는 개념으로?

게임 2048 느낌으로?

coin.length 가 12인 이유가 있을것같은데..

[1,4,5] amount=12

이런 케이스 때문에 결국 완탐을 해야하는 건 맞는것 같은데…

그럼 그냥 결국 내 아이디어는 맞는데 최적화 문제인건가?

로그 뽑아서 중복제거해서 최적화 한번 해보자.

시간복잡도

1차 시도 구현처럼

완전탐색시 시간복잡도?

→ 코인 길이 최대 12

코인 가장 작을때 기준 1~12

aoumt = 10^4 라고 가정하면

10^4//12 ⇒ 833번반복

그 833번 안에 숫자 12개가 들어감

그걸 또 다시 833번

depth 1개당 12개

12^833 → 될리가 없잖아 ㅋㅋㅋㅋㅋㅋㅋ

아예 로직 다시 갈아엎고 해야될듯

자료구조

코드 구현 [필수 작성]

1차 시도

테케들 다 통과하고, 내가 만든 테케도 다 통과해서 제출해봤는데…

→ 시간초과

-b3a7-852800e015b4/38e96af2-8288-401b-986b-f442936679ca/Untitled.png)

#9시40분 -> 10시20분

import sys

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        min_coin_num = sys.maxsize
        
        def backtrack(curr_max_value, curr_max_value_index, curr_amount, curr_coin_num):
            nonlocal min_coin_num

            if curr_amount == 0:
                min_coin_num = min(min_coin_num, curr_coin_num)
                return

            if min_coin_num < curr_coin_num:
                return

            while curr_amount < curr_max_value:
                curr_max_value_index -= 1
                if curr_max_value_index < 0:
                    return
                curr_max_value = coins[curr_max_value_index]

            for coin_index in range(curr_max_value_index,-1,-1):
                curr_amount -= coins[coin_index]
                curr_coin_num += 1
                backtrack(curr_max_value, curr_max_value_index, curr_amount, curr_coin_num)
                curr_amount += coins[coin_index]
                curr_coin_num -= 1
        
        backtrack(coins[-1], len(coins)-1, amount, 0)

        if min_coin_num == sys.maxsize:
            return -1

        return min_coin_num

2차 시도

로그 통해 확인해보니 코드가 내 의도대로 동작하지 않아서
아래 부분 수정해주니 테케 조금 더 통과했으나 여전히 시간초과

→ 내일 코테 시험인데 시간 너무 오래걸려서 그냥 해설영상 보러감

curr_max_value = coins[coin_index]
curr_max_value_index = coin_index

#9시40분 -> 

import sys

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        min_coin_num = sys.maxsize
        
        def backtrack(curr_max_value, curr_max_value_index, curr_amount, curr_coin_num):
            nonlocal min_coin_num
            
            if curr_amount == 0:
                min_coin_num = min(min_coin_num, curr_coin_num)
                # print("현재 amount 빼다가 0이 되서 종료")
                # print("curr_max_value=",curr_max_value)
                # print("curr_amount=",curr_amount)
                # print("curr_coin_num=",curr_coin_num)
                return

            if min_coin_num < curr_coin_num:
                # print("min_coin_num < curr_coin_num 되서 종료")
                # print("curr_max_value=",curr_max_value)
                # print("curr_amount=",curr_amount)
                # print("curr_coin_num=",curr_coin_num)
                return

            while curr_amount < curr_max_value:
                curr_max_value_index -= 1
                if curr_max_value_index < 0:
                    # print("curr_max_value_index < 0 되서 종료")
                    # print("curr_max_value=",curr_max_value)
                    # print("curr_amount=",curr_amount)
                    # print("curr_coin_num=",curr_coin_num)
                    return
                curr_max_value = coins[curr_max_value_index]

            for coin_index in range(curr_max_value_index,-1,-1):
                curr_amount -= coins[coin_index]
                curr_coin_num += 1
                curr_max_value = coins[coin_index]
                curr_max_value_index = coin_index
                # print("=========function call==========")
                # print("방금 뺀 코인 값=",coins[coin_index])
                # print("curr_max_value=",curr_max_value)
                # print("curr_amount=",curr_amount)
                # print("curr_coin_num=",curr_coin_num)
                backtrack(curr_max_value, curr_max_value_index, curr_amount, curr_coin_num)
                curr_amount += coins[coin_index]
                curr_coin_num -= 1
        
        # print("========스타트=============")
        # print("curr_max_value=",coins[-1])
        # print("curr_amount=",amount)
        # print("curr_coin_num=",0)
        backtrack(coins[-1], len(coins)-1, amount, 0)

        if min_coin_num == sys.maxsize:
            return -1

        return min_coin_num

3차 시도

해설영상 보고 나서 구현

BFS 로 구현

BFS 로 구현하려면 어떻게 해야할까? 큐를 활용해야하나?

amount 를 각 원소로 빼준 값들을 순서대로 queue 에 넣는다.

이때 queue 에 넣는 자료형태는 (amount, depth) 인데,

이때, depth 는 현재까지 사용한 코인 갯수와 동일

Q1.

yes까지 리턴했는데 while 문 안에서 return 했는데왜 함수가 종료가 안되고 계속 도는지도 이해가 안되고

Q2.

return 됐어야하는데 그 이후에 갑자기 뜬금포로 나오는

2 1 3
deque([[1, 1]])
2 2 1

이 값들도 어디서 튀어나온건지 도무지 이해가 안갑니다.

while True → while pipe 로 바꾸면 해결이 되기는 하지만,

while True 여도 return 시키면 함수가 종료되면서 루프를

빠져나와야할텐데 왜 이런 오류가 나는건지 모르겠습니다.

from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        pipe = deque([[amount,0]])

        while True:
            curr_amount, depth = pipe.popleft()
            depth += 1
            for i in range(len(coins)-1,-1,-1):
                #print(coins[i],depth,curr_amount)
                curr_amount -= coins[i]
                if curr_amount == 0:
                    #print('yes')
                    return depth
                if curr_amount < 0:
                    #print("-----")
                    curr_amount += coins[i]
                    continue
                pipe.append([curr_amount,depth])
                print(pipe)
                curr_amount += coins[i]
        
        return -1

5 1 11
deque([[6, 1]])
2 1 11
deque([[6, 1], [9, 1]])
1 1 11
deque([[6, 1], [9, 1], [10, 1]])
5 2 6
deque([[9, 1], [10, 1], [1, 2]])
2 2 6
deque([[9, 1], [10, 1], [1, 2], [4, 2]])
1 2 6
deque([[9, 1], [10, 1], [1, 2], [4, 2], [5, 2]])
5 2 9
deque([[10, 1], [1, 2], [4, 2], [5, 2], [4, 2]])
2 2 9
deque([[10, 1], [1, 2], [4, 2], [5, 2], [4, 2], [7, 2]])
1 2 9
deque([[10, 1], [1, 2], [4, 2], [5, 2], [4, 2], [7, 2], [8, 2]])
5 2 10
deque([[1, 2], [4, 2], [5, 2], [4, 2], [7, 2], [8, 2], [5, 2]])
2 2 10
deque([[1, 2], [4, 2], [5, 2], [4, 2], [7, 2], [8, 2], [5, 2], [8, 2]])
1 2 10
deque([[1, 2], [4, 2], [5, 2], [4, 2], [7, 2], [8, 2], [5, 2], [8, 2], [9, 2]])
5 3 1
-----
2 3 1
-----
1 3 1
yes
2 1 3
deque([[1, 1]])
2 2 1
-----

4차 시도

중복되는 경우 제거해주면 될것같은데..

내일 코테 있는데 SQL 도 준비해야되서 우선 여기서 중지…

from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        pipe = deque([[amount,0]])
        if amount == 0:
            return 0

        while pipe:
            curr_amount, depth = pipe.popleft()
            depth += 1
            for i in range(len(coins)-1,-1,-1):
                #print(coins[i],depth,curr_amount)
                curr_amount -= coins[i]
                if curr_amount == 0:
                    #print('yes')
                    return depth
                if curr_amount < 0:
                    #print("-----")
                    curr_amount += coins[i]
                    continue
                pipe.append([curr_amount,depth])
                #print(pipe)
                curr_amount += coins[i]
        
        return -1

5차 시도

같은 curr_amount 에 대해서 중복해서 계산해줄 필요가 없으므로, memoization 기법을 활용해 중복을 제거해주었음.

처음에는 list 로 기록을 했으나, 해당 amount 를 계산했는지 탐색하기 위해서는 O(n) 의 시간복잡도가 iteration 당 소모되어 시간 초과가 발생.

따라서 O(1) 의 시간복잡도로 해당 amount 를 계산했었는지 파악하기 위해 Dictionary(Hash Map)을 활용함.

from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        pipe = deque([[amount,0]])
        amount_memo = {}

        if amount == 0:
            return 0

        while pipe:
            curr_amount, depth = pipe.popleft()
            depth += 1
            
            for i in range(len(coins)-1,-1,-1):
                #print(coins[i],depth,curr_amount)
                curr_amount -= coins[i]
                if curr_amount == 0:
                    #print('yes')
                    return depth
                if curr_amount < 0:
                    #print("-----")
                    curr_amount += coins[i]
                    continue
                if amount_memo.get(curr_amount,True):
                    pipe.append([curr_amount,depth])
                    amount_memo[curr_amount] = False
                #print(pipe)
                #print(amount_memo)
                curr_amount += coins[i]
        
        return -1

배우게 된 점 [ 필수 X ]

특정 원소가 visited 됐는지 조사하기 위해서 굳이 복잡하게 아래와 같이 구현할 필요 없다

if amount_memo.get(curr_amount,True):

아래와 같이 중복을 허용하지 않는 set 을 활용하면 된다!

왜냐하면 어차피 set 이 hash table 을 활용하여 구현되어있기 때문이다.

visited = set()
~~
if next not in visited and next >= 0:
	~~

질문 [ 필수 X ]

Q1.

yes까지 리턴했는데 while 문 안에서 return 했는데왜 함수가 종료가 안되고 계속 도는지도 이해가 안되고

Q2.

return 됐어야하는데 그 이후에 갑자기 뜬금포로 나오는

Q3. (추가질문)

위 두 질문에 대한 답변이 잘 이해가 안됩니다. return 문이 정상적으로 실행되었는데, 함수가 종료되지 않고 추가적인 print 를 찍어낼 수 있는 경우가 있나요? 즉, return 이 정상적으로 실행되었는데도, 함수가 종료되지 않고 계속 실행되는 경우가 있나요? → 리트코드 테스트케이스 채점방식에 관한 문제였음 ㅠㅠ
[GPT 답변]

피드백 [ 코치 작성 ]

코드 자체는 정상적으로 진행되고 있습니다. 두 문제점의 공통적인 원인은 빈 큐에서 pop연산을 수행하려 한 것이며 그로 인해 발생하는 문제점입니다. 질문에 답변을 드리자면 yes출력 이후 나오는 출력들은 다음 테스트 케이스입니다. 출력이 그대로 이어졌기에 return 이후에도 함수가 종료되지 않은 것으로 보인 것입니다.

추가질문

leetcode는 runtime error가 발생할 때 즉시 코드 실행을 정지합니다. 그리고 여태껏 실행된 출력문을 한번에 보여줍니다. 이 때 문제는 모든 테스트 케이스를 한번에 출력한다는 것입니다.

즉

5 1 11
deque([[6, 1]])
2 1 11
deque([[6, 1], [9, 1]])
1 1 11
deque([[6, 1], [9, 1], [10, 1]])
5 2 6
deque([[9, 1], [10, 1], [1, 2]])
2 2 6
deque([[9, 1], [10, 1], [1, 2], [4, 2]])
1 2 6
deque([[9, 1], [10, 1], [1, 2], [4, 2], [5, 2]])
5 2 9
deque([[10, 1], [1, 2], [4, 2], [5, 2], [4, 2]])
2 2 9
deque([[10, 1], [1, 2], [4, 2], [5, 2], [4, 2], [7, 2]])
1 2 9
deque([[10, 1], [1, 2], [4, 2], [5, 2], [4, 2], [7, 2], [8, 2]])
5 2 10
deque([[1, 2], [4, 2], [5, 2], [4, 2], [7, 2], [8, 2], [5, 2]])
2 2 10
deque([[1, 2], [4, 2], [5, 2], [4, 2], [7, 2], [8, 2], [5, 2], [8, 2]])
1 2 10
deque([[1, 2], [4, 2], [5, 2], [4, 2], [7, 2], [8, 2], [5, 2], [8, 2], [9, 2]])
5 3 1
-----
2 3 1
-----
1 3 1
yes # 1번 테스트 케이스 종료
2 1 3 # 2번 테스트 케이스 시작
deque([[1, 1]])
2 2 1
-----

이는 솔루션 함수를 통해 여러가지 테스트 케이스를 반복으로 돌리기에 발생하는 일이며 솔루션 함수 최상단에 print(”new test case”)와 같이 출력을 추가하면 이해가 쉬울 것입니다.