[LeetCode] 279. Perfect Squares, Medium

1. 문제

• 정수 n이 주어질 때, 완전 제곱수의 합으로 만들 수 있는 최소 개수를 반환하라.

2. 해결

function numSquares(n: number): number {
    const queue:[number, number][] = [[n, 0]];
    const visit = new Set();
    
    while(queue.length > 0) {
        const [curr, step] = queue.shift();
        
        const sqrt = Math.floor(Math.sqrt(curr));
        
        for(let i = sqrt; i > 0; i--){
            const next = curr - i * i;
            
            if(next === 0) return step +1;
            
            if(!visit.has(next)) {
                visit.add(next);
                queue.push([next, step+1])
            }
        }
    }
    
    return -1;
};

• 못 풀었다. 인접 노드를 어떻게 가져가야 할 지..
• 원리는 큐에 n과 횟수를 짝지어 넣고, n의 제곱근 부터 0보다 클 때 까지 줄여 나가면서 0이 되는 구간을 찾는다.