[leetcode] 2749* (Medium)

https://leetcode.com/problems/minimum-operations-to-make-the-integer-zero/description/

아이디어 단계 - greddy

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        
        // i 값 선택 - 2^n 값이 num1-num2에 가장 가까운 값으로 선택
        // 안되는지는 어떻게 판단하지...
        // 0 될때까지 ㄱ -> 그전에 저장한 값이랑 동일하면, 안된다는 거니 return -1
        // 아니면 count값 return
        int min = 1 - (num1-num2); 
        int index = 0; //i값
        ArrayList last = new ArrayList<>();
 
        int count = 0;
        while(true){
            if(num1==0) return count;

            // i값 선택
            for(int i=0;i<=60;i++){
                int n = (int)Math.pow(2,i) - (num1-num2);
                if(min > Math.abs(n)) {
                    min = n;
                    index = i;
                } else break;
            }

            // 계산
            num1 = num1 - ((int)Math.pow(2,index) + num2);
            if(last.contains(num1)) break; // 그 전에 나온 값이 나온다면 불가로 판정
            last.add(num1); 
            count++;
        }
        
        return -1;
    }
}

=>
답안

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        
        for (int k = 1; k <= 60; k++) {
            long x = (long) num1 - (long) k * num2;
            if (x < k) continue;                 // 최소 1을 k개 더해야 함
            if (Long.bitCount(x) <= k) return k; // k개의 2의 거듭제곱 합으로 표현 가능
        }
        return -1;
    }
}

class Solution {
    public int makeTheIntegerZero(int num1, int num2) {
        // k는 1~60만 보면 충분 (long 범위에서 2^60 쯤이 상한)
        for (int k = 1; k <= 60; k++) {
            long x = (long) num1 - (long) k * num2; // int 오버플로 방지

            if (x < k) continue;              // 최소합(k)보다 작으면 불가능
            if (popcount(x) <= k) return k;   // 1비트 개수가 k 이하면 가능 → 최소 k니까 바로 반환
        }
        return -1; // 어떤 k로도 불가능
    }

    // Kernighan popcount
    private int popcount(long x) {
        int c = 0;
        while (x > 0) {
            x &= (x - 1);
            c++;
        }
        return c;
    }
}