[LeetCode] Perfect Squares - 2021.08.29

문제 링크 : LeetCode
나의 풀이 : Git Solution

문제내용

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 <= 10⁴

풀이

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) {
    // write your code here
        int n = 12;
        int answer = process(n);
        System.out.println("answer : " + answer);

    }

    public static int process(int n ){

        HashSet<Integer> perfectSquareList = new HashSet<>();
        Queue<Integer> que = new LinkedList<>();
        int cnt = 0;
        que.add(0);

        while(!que.isEmpty()){
            cnt++;

            int curQueSize = que.size();
            for(int i=0; i<curQueSize; i++){
                int curValue = que.poll();
                for(int j = 1; j*j<=n-curValue; j++){
                    int sum = curValue + j*j;

                    if(perfectSquareList.contains(sum))
                        continue;

                    if(sum == n)
                        return cnt;
                    else{
                        que.add(sum);
                        perfectSquareList.add(sum);

                    }
                }
            }

        }

        return -1;
    }

}

실행결과

Accepted    51 ms    40.9 MB