[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 len = countOne(Integer.toBinaryString(n));
        
        while(countOne(Integer.toBinaryString(++n)) != len) {
        }
        
        return n;
    }
    
    public int countOne(String nBin) {
        int count = 0;
        for(int i = 0; i < nBin.length(); i++) {
            if(nBin.charAt(i) == '1') {
                count++;
            }
        }
        
        return count;
    }
}

n의 값을 1씩 증가시키며 이진화를 시킨다음 해당 1이 몇개있는지 세는 단순한 알고리즘이다.

그리고 결과는 아래와 같았다.

 

처음엔 replace() 메서드를 쓰는 방법으로 해결했었다. "0"을 "" 빈 문자열로 바꿔주고 전체 길이를 계산하는 방법이였다. 예상대로 시간이 오래걸렸었다. 아래는 해당 코드와 결과이다.

 

class Solution {
    public int solution(int n) {
        String nBin = Integer.toBinaryString(n);
        nBin = nBin.replace("0", "");
        int len = nBin.length();

        while(Integer.toBinaryString(n+1).replace("0", "").length() != len) {
            n++;
        }
        return n+1;
    }
}

 

 

 

출처

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