279. Perfect Squares

• python3

📎 Problem

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

• 1 <= n <= 104

Plan Solution

1. n보다 작은 제곱수 리스트를 생성
2. 큐에 타겟 숫자를 넣고 제곱수와 크기를 비교한다
   • 제곱수와 같을 경우는 리턴
   • 제곱수가 더 큰 경우에는 의미가 없으므로 루프를 종료
   • 제곱수가 더 작은 경우에 큐에 다음 값을 넣음

Code

class Solution:
    def numSquares(self, n: int) -> int:
        if n <= 1:
            return n

        # Step 1: Generate all perfect squares less than or equal to n
        squares = []
        i = 1
        while i * i <= n:
            squares.append(i * i)
            i += 1

        # Step 2: Initialize BFS
        def bfs():
            q = deque([n])
            steps = 0

            while q:
                steps += 1
                for _ in range(len(q)):
                    curr = q.popleft()
                    for square in squares:
                        if curr == square:  # Found a perfect square
                            return steps
                        if curr < square:  # No need to consider larger squares
                            break
                        q.append(curr - square)
            return steps
        
        return bfs()

Result

• Time Complexity : O(√n * n)
• Space Complexity : O(n)