[프로그래머스/Lv.2] 다음 큰 숫자

1. Input

1) 자연수 n

 

2. Output

1) n의 다음 큰 숫자

2) 다음 큰 숫자의 정의

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수

조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다.

조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수

 

3. Constraint

1) n은 1,000,000 이하의 자연수

 

4. Example

Input: n=15 -> Output: 23

설명:

- 15는 2진수로 1111이다. 15보다 큰 자연수들 중 2진수로 변환했을 때 1의 개수가 처음으로 4개인 수를 반환해야 한다.

16 = 10000    17 = 10001     18 = 10010    19 = 10011    20 = 10100     21 = 10101    22 = 10110    23 = 10111

이므로 23을 반환한다.

 

5. Code

1) 첫 코드(2022/11/29)

int answer = 0;
String s1 = Integer.toBinaryString(n).replaceAll("0","");
while(true){
    String s2 = Integer.toBinaryString(++n).replaceAll("0","");
    if(s1.length()==s2.length()){
        answer = n; break;
    }
}        
return answer;

  - 정확성은 만점이었지만, 효율성에서 0점이었음

2) String 연산을 int 연산으로 바꾼 코드(2022/11/29)

int answer = 0, n1 = n, c1 = 0;
while(n1>0){
    c1 += n1%2; n1 /= 2;
}
while(true){
    int n2 = ++n, c2 = 0;
    while(n2>0){
        c2 += n2%2; n2 /= 2;
    }
    if(c1==c2){
        answer = n; break;
    }
}        
return answer;

  - 속도도 훨씬 빨랐고, 효율성에서도 만점이 나옴

 

* Integer.bitCount(n) 메서드는 n이 2진수일때 1의 개수를 세어주는 메서드