coin change

LeetCode - The World's Leading Online Programming Learning Platform

문제 파악

문제이해

가장 적은수의 코인갯수로 amount 만들기

제한 조건 확인

코인갯수 1~12개

아이디어

전형적인 메모이제이션 문제
각 level(또는 height)에서 BFS로 선택가능한 코인을 고르고
결과값을 메모해두고 중복 연산하지 않는다.

시간복잡도

12^12 중 상당수의 중복을 줄여 풀수 있지 않을까?
근데 2^31-1 으로 숫자범위가 굉장히 커서 모를지도?

→ 아니다

다시 생각해보니,

amount가 10^4 이므로,
메모이제이션 될 수 있는 수는 10^4개
아무리 반복 많이 해봤자 10^4 안에 끝날 수 있다.

자료구조

visited = set
q for bfs

접근 방법

아이디어

코드 구현

1차 시도

from collections import deque
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        visited_amount = set()
        q = deque([])
        r_coins = list(reversed(coins))
        coin_num = 0
        if amount == 0:
            return 0
        while True:
            #print(q)
            coin_num += 1
            if coin_num == 1:
                for i in range(len(r_coins)):
                    next_amount = amount - r_coins[i]
                    if next_amount > 0 and next_amount not in visited_amount:
                        q.append(amount - r_coins[i])
                        visited_amount.add(next_amount)
                    elif amount - r_coins[i] == 0:
                        return coin_num
            elif coin_num > 1:
                level_iter = len(q)
                for i in range(level_iter):
                    tmp_amount = q.popleft()
                    for i in range(len(r_coins)):
                        next_amount = tmp_amount - r_coins[i]
                        if next_amount > 0 and next_amount not in visited_amount:
                            q.append(tmp_amount - r_coins[i])
                            visited_amount.add(next_amount)
                        elif tmp_amount - r_coins[i] == 0:
                            return coin_num
            if not q:
                break
        return -1

배우게 된 점

노션에서 수학 공식블록을 활용하면 문서화할때 시각화에 도움이 된다.x

질문 [ 필수 X ]

Q. 시간복잡도

시간복잡도를 추론하는 흐름이 충분히 논리적인지 궁금합니다.

답변

적절하지만 약간 수정할만한 부분은

모든 amount에 대해 coin의 개수만큼 탐색하는 것이 최악의 경우이므로

의 시간복잡도를 갖는다고 볼 수 있습니다.