다음 큰 숫자 Java

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
  예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항

• n은 1,000,000 이하의 자연수 입니다.

입출력 예

첫번째 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        int ls = n;
        while (true) {
            String bs = Integer.toBinaryString(n);
            bs = bs.replaceAll("0", "");
            ls++;
            String bs2 = Integer.toBinaryString(ls);
            bs2 = bs2.replaceAll("0", "");
            System.out.println(bs2);
            int ln = bs.length();
            int ln2 = bs2.length();
            if (ln == ln2) {
                answer = ls;
                break;
            }
        }
        return answer;
    }
}

• 문제를 읽자마자 주어진 n을 2진수로 변환후 0을 지우고 1의 개수를 구한후
  n에 1씩더하여 똑같이 2진수로 변환후 0을 지우고 1의 개수를 구하여 같을때를 구하면 되겠다생각하여 몹시 쉽다고 생각하였다. 그러나 효율성 테스트에서 시간이 오래걸려 0점을 받고 어떻게해야 더 빨리 구할 수 있는지 찾아보았다.

두번째 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
         int ls = n;
         int ln = Integer.bitCount(n);
      // n을 2진수로 바꾼후 1의 개수 세기
        for(int i = n+1 ; true; i++){
            if(ln==Integer.bitCount(i)){
                  answer= i;
                break;
            }
     // n을 1씩더하여 2진수로 변환한 후 1의개수고 같을경우 멈춤
        }
        return answer;

    }
}

• 그리하여 찾은것이 Integer.bitCount라는 함수였다.
  Integer.bitCount( )를 사용하여 replace( )와 Integer.toBinaryString( ) 2개를 사용하는 것을 1개로 줄여 풀어보니 정답이었다.