[LeetCode][Python3] 279. Perfect Squares

Problem :

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

My Solution :

class Solution:

def numSquares(self, n):

"""

:type n: int

:rtype: int

"""

if n == int(n**0.5)**2:

return 1

squares = []

for a in range(1, int(n**0.5)+1):

squares.append(a**2)

level = 0

queue = {n}

while True:

level += 1

level_queue = set()

for num in queue:

for a in squares:

if a == num:

return level

if a > num:

break

level_queue.add(num - a)

queue = level_queue

Comment :

BFS를 하면서 최초로 square를 만났을 때 level을 리턴하는 전략을 취해보았다.