Leetcode 279) Perfect Squares

30 Jul 2021 in Algorithms

내 답안

• 힌트 보고 품.. 또륵..그래두 그리디로 푼 거 보단 아주 깔끔하다… 마치 아이스 아메리카노 같은
• 약간 그 피보나치 계단 오르는 거랑 비슷한 느낌도 들고
• 딕셔너리에 저장해서 풀었다.

class Solution {
    Map <Integer,Integer> m = new HashMap<>();

    public int numSquares(int n){

        if(n==0){
            return 0;
        }
        if(m.containsKey(n)){
            return m.get(n);
        }
        int max = (int)Math.sqrt(n);

        int[] s = new int[max];

        for(int i=1;i<max+1;i++){
            s[i-1]=i*i;
        }

        int min = Integer.MAX_VALUE;


        for(int i=0;i<max;i++){
            int tmp=1+numSquares(n-s[i]);
            if(min>tmp){
                min = tmp;
            }
        }

        m.put(n,min);
        return min;
    }


}

다른 답안

• 나 빼고 다 똑똑하다.

class Solution {
    public int numSquares(int n) {
        int[] m = new int[n+1];
        for(int i=1;i<=n;i++){
            m[i] = Integer.MAX_VALUE;
            for(int j=1;j*j<=i;j++){
                int square = j*j;
                int remaining = i-square;
                int total = 1 + m[remaining];
                m[i] = Math.min(m[i],total);
            }
        }
        return m[n];
    }
}

오답

• 음.. timelimit뜬다
• 답안에 의하면, 이미 계산한 것들을 계속 다시 계산해서라고 함. 음.. 그렇구나
  • 그럼 계산한결과를 map에 저장해서 lookup 하는 식으로 한번 바꿔봐야겠다.

class Solution {
    int min = Integer.MAX_VALUE;
    public int numSquares(int n) {
        //1, 2, 3, 4, ..., 100 => 1, 4, 9, 16 ..., 10000
        int guess = (int)Math.sqrt(n);
        int[] pool = new int[guess];
        for(int i =pool.length;i>0;i--){
            pool[pool.length-i]= i*i;
        }
        //queue 문제인지는 모르겠고, 여기서 부터 그 백트래킹에서 푼 문제랑 비슷해지는 것 같은데?
        helper(n,pool,0);
        return min;
    }

    public void helper(int target,int[] pool,int cnt){
        if(target<0){return;}

        if(target==0){
            if(min>cnt){
                min=cnt;
            }
            return;
        }
        cnt++;

        for(int i =0;i<pool.length;i++){
            int a = target-pool[i];
            if(a<0){continue;}
            helper(a,pool,cnt);
        }
    }
}