우선 내가 하고싶은대로 머리를 써보았다. 우선, 문제부터 보면,
https://leetcode.com/problems/perfect-squares/
우선 나는 이상하게 이런문제를 보면 수학적으로 뭔가 하고싶다. 그리고 사실 BFS섹션인데 이런문제가있어서, 어떻게하면 이런문제를 BFS사고로 생각하지? 라는 생각으로 좀 머리아프게 한번 시간을 보내보았다. 그래서 다음과 같이 접근을 해보았다.
from collections import deque
def numSquares(n):
q = deque()
for i in range(int(n ** 0.5), 0, -1):
q.append(i)
while q:
count = 0
Yerin = q.popleft()
Baek = Yerin * Yerin
if (n - Baek) % 2 == 0:
count += 1
new_n = n - Baek
if new_n % Yerin == 0:
count += (new_n // Yerin)
elif (n - Baek) % 2 == 1:
continue
return count
print(numSquares(12))Yerin 과 Baek 저거는 제곱(squares)문제이기때문에 백예린의 Squares라는 노래가 생각나서...저렇게 혼자 붙여보았다. 아무튼, 수학적으로 뭔가 할 수 있을것 같다는 생각이 들어서 최대한 해보았다. 우선 데크를 사용했다. 그러고나서 다른 BFS를 풀때와 마찬각지로, while문을 돌렸고 popleft()를해서 그때그때마다 수를 뽑아서 for문과 if문에 따라서 조건을 맞춰주려했다. 내가 생각해낸 조건은 다음과같다. 우선 n 이하의 제곱가능한 수들을 구한다. 12라고 하면 1, 2, 3 이 다음과같다. 하지만, 역순으로 생각을 해서 3, 2, 1이다. 왜냐하면, 25같은 경우에는 5제곱으로 끝나고, 그렇게되면 답은 1이다. 한번에 끝난다. 그렇기때문에 역순으로 해서 만약에 나누어주었을때 나머지가 없으면 한번더 검사한다. 한번더 제곱으로 나눠질수있는지 봐준다. 그렇게해서 다음과같이 총 count의 갯수를 세주었다. 그런데 역시 답은 나오지않았다. 12를 예를 들어 저걸 돌리면 계속 5가 나온다. 그러고 1시간 넘게 수학적으로 어떻게 해볼까 라는 생각으로 접근하다가 답을 보았는데, 흠.
class Solution:
def numSquares(self, n):
# list of square numbers that are less than `n`
square_nums = [i * i for i in range(1, int(n**0.5)+1)]
level = 0
queue = {n}
while queue:
level += 1
#! Important: use set() instead of list() to eliminate the redundancy,
# which would even provide a 5-times speedup, 200ms vs. 1000ms.
next_queue = set()
# construct the queue for the next level
for remainder in queue:
for square_num in square_nums:
if remainder == square_num:
return level # find the node!
elif remainder < square_num:
break
else:
next_queue.add(remainder - square_num)
queue = next_queue
return level이것의 주요 접근법은 우선 12라고 했을때 제곱수 가능한 숫자 3개가 나온다. 1, 2, 3. 이 숫자들의 공통점은 각자 제곱이 가능하다. 그리고 12 이하이다. 1, 4, 9 < 13. 이것을 코딩으로 풀어내기위해서는, 각자 빼준다. 빼준 수 또한, 제곱수가 가능한지를 심사한다. 13 - 1 = 12 불가능이다. 11은 제곱수의 합이 아니다. 13 - 4 = 9 3의 제곱의 합 가능. 13 - 9 = 4 2의 제곱의 합 가능. 이런식으로 가능할경우 다음과 같은 수들에게 level += 1을 시켜준다. 그러고나서 두번째로 제곱의 합이 가능할경우 level += 1...이런식으로 if문과 for문을 조합하여 쭈욱쭈욱 내려간다. 그게바로 저 답이다...여기까지 거의다 생각할 수 있었는데 아깝네.
