다음 큰 숫자

https://school.programmers.co.kr/learn/courses/30/lessons/12911

1차시도 브르투 포스

1부터 1000000 까지 전부 1의 개수를 구해서 풀었다.

정확도는 맞는데 효율성 테스트 전부 실패

import java.util.*;

class Solution {
    
    static final int SIZE = 1000001;
    
    public int solution(int n) {
        int answer = 0;
 
        int[] dp = new int[SIZE];
        
        for(int i = 0; i < SIZE; ++i)
        {
            dp[i] = CountOne(i);
        }
 
        int cur = dp[n];
        
        int next = n+1;
        while(true)
        {
            if(cur == dp[next])
                break;
            next++;
        }
        
        answer = next;
        
        return answer;
    }
    
    public static int CountOne(int n)
    {
        int answer = 0;
        while(true)
        {
            if(n%2 == 1)
                answer++;
            
            if(n < 2)
            {
                break;
            }

            n/=2;
        }
        
        return answer;
    }
}

그래서 다른 방식으로 풀려고 했는데 너무 복잡한 코드라 뭔가 쓸데없는 고민인것 같았다

1을 옮길 수 있는 것을 찾아서 왼쪽으로 이동시키고
그 1보다 오른쪽에 있는 것들은 전부 오른쪽으로 이동시키고 등등... 한참을 고민하며 코딩하다가 뭔가 너무 복잡하고 잘못된 방향으로 풀고 있는거 같았다.

풀이를 봤는데 허탈하네
그냥 브루트 포스를 최적화만 하면 되는 문제 였다 하...

O(log₂n)

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        int oCount = CountOne(n);
        
        int next = n+1;
        while(true)
        {
            if(oCount == CountOne(next))
            {
                answer = next;
                break;
            }
            
            next++;
        }
        
        return answer;
    }
    
    public static int CountOne(int n)
    {
        int answer = 0;
        while(true)
        {
            if(n%2 == 1)
                answer++;
            
            if(n < 2)
            {
                break;
            }

            n/=2;
        }
        
        return answer;
    }
}