[LeetCode]Perfect Squares

https://leetcode.com/problems/perfect-squares/description/

Perfect Squares - LeetCode

 

문제 분석

n이 주어질 때 완전 제곱수 몇개를 더하여 n을 만들 수 있는지 구하는 문제입니다.

 

처음 시도한 답안 - DP

class Solution:
    def numSquares(self, n: int) -> int:
        square_numbers = []
        
        for i in range(1, n): # 제곱수 저장
            if i**2 > n:
                break
            square_numbers.append(i**2)
        # square_numbers = [1,4,9,16....]

        ans = [x for x in range(n+1)]
        # idx    0,1,2,3,4,5,6,7,8,9,10,11,12
        # ans = [0,1,2,3,1,2,3,4,2,1, 2, 3, 3]
        # ans[3] -> 3을 만들기 위한 최소 제곱수 카운트 저장할거임

        for i in range(1, len(ans)): # 1 ~ 12 반복
            for square_number in square_numbers: # [1,4,9,16..]
                if square_number <= i: # i가 5라고 가정, square_number를 사용 가능한게 1, 4 밖에 없음.
                    # 현재 저장 vs 2 vs 2개
                    ans[i] = min(ans[i], ans[i-square_number]+1)

        # ans : [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]

        return ans[-1]

접근 방법

1. DP를 활용해 풀이하는 방법입니다.
2. 먼저 n까지 순회를 통해 제곱수인 것들을 square_numbers에 저장합니다.
3. 주어진 숫자 +1 만큼 ans 배열인 DP를 생성합니다. 이때 DP에는 각 인덱스를 할당합니다.
4. 1부터 N까지 반복하고, 이중 순회로 사용이 가능한 제곱수 목록을 반복합니다.
   1. 만약 등장한 제곱수가 사용이 가능하다면
      1. 현재 저장된 값 vs 등장한 숫자-제곱수를 만드는데 사용된수 +1 중 작은 것을 저장합니다.
5. 반복을 종료하면 ans DP의 마지막 요소에 가장 적은 갯수를 구할 수 있습니다.

DP의 경우 각 인덱스에 해당하는 숫자를 만들기 위해 사용된 제곱수의 갯수를 저장하게 됩니다. 처음에 인덱스로 초기화한 이유는 1을 사용하는 경우로 가정한 것입니다. 즉 DP[8]=8 이라면, 8을 만들기 위해 1을 8번 더했다는 의미입니다.

 

이후에 반복을 수행하면서 현재 등장한 숫자와 그보다 작은 사용 가능한 제곱수 목록을 확인해서 사용이 가능하다면 해당 제곱수를 더하기 전 DP를 확인해서 그 값에 +1한 값을 사용합니다. 혹은 현재 저장된 수를 그대로 이용합니다.

 

이 문제의 해법은 이전에 풀이한 Coin Change 문제와 거의 동일합니다.

https://leffept.tistory.com/522

 

두번째로 시도한 답안 - BFS

from collections import deque


class Solution:
    def numSquares(self, n: int) -> int:
        queue = deque([[0, n]]) # 탐색의 깊이(레벨)과 만들어야 하는 숫자
        
        while queue:
            level, num = queue.popleft()

            # 만들어야하는 숫자에 루트를 씌우고 int형 변환한 값과, 만들어야하는 숫자에 루트를 씌운 값이 동일하다면
            # 다음 레벨에서는 무조건 n을 만들 수 있습니다.
            if int(num ** 0.5) == num ** 0.5:
                return level+1

            # 만들어야하는 숫자에 루트를 씌운 수만큼 반복합니다.
            for i in range(1, int(num**0.5)+1):
            	# 큐에 탐색할 다음 레벨과, 만들어야하는 숫자-제곱수를 넣습니다.
                queue.append([level+1, num-i*i])

접근 방법

1. BFS 알고리즘을 활용해 풀이하는 방법입니다.
2. 처음에는 탐색하는 레벨과 만들어야하는 숫자 n을 큐에 넣습니다.
3. 큐가 있는 동안 반복합니다.
   1. 만약 현재 만들어야할 숫자가 루트를 씌웠을 때 정확히 떨어진다면
      즉, 제곱수가 된다면 다음 레벨에서 무조건 만들 수 있으므로 level+1 값을 리턴합니다.
   2. 만들어야 하는 숫자에 루트를 씌운 수만큼 반복합니다.
      1. 큐에 탐색할 다음 레벨과 만들어야하는 숫자 - 등장한 숫자의 제곱을 넣습니다.

해당 방식의 경우 트리를 그려가면서 이해를 하는 것이 수월합니다. 저도 처음에는 BFS 방식으로 풀이를 하였지만 숫자를 덧셈 누적 시켜가면서 트리를 만들었고 만든 숫자가 n이 되는 경우에 해당 레벨을 리턴하도록 구성했습니다.

하지만, 너무 많은 반복으로 인해서 Time Limit Exceeded가 나오게 되어서 최적화하는 방법을 찾아보았습니다.

 

위 풀이는 덧셈을 하는 방법과는 반대로 만들어야하는 숫자에서 등장한 제곱수들을 뺄셈하면서 구하는 방법입니다. 특히 루트를 씌우면서 값을 비교하고 for loop 한다는 것이 신기한 방법이었습니다. 

또한, 루트를 씌운 경우에 딱 떨어지는 제곱수가 나온다면 해당수는 다음 레벨에 무조건 존재하므로 더이상 탐색하지 않아도 되어서 시간 복잡도를 줄일 수 있는 방법입니다.

 

두가지의 풀이를 했었지만 DP를 활용한 방법이 더 직관적이고 이해하기에 쉬운 것 같습니다.