다음 큰 숫자

https://school.programmers.co.kr/learn/courses/30/lessons/12911?language=java 

프로그래머스

 

n보다 큰 수 중 2진수의 1의 갯수가 n의 2진수의 1의 갯수와 동일한 수 중 가장 작은 수를 찾으면 된다.

 

처음엔 Integer.toBinaryString 으로 2진수를 구하고, replaceAll로 0을 모두 제거한 뒤의 문자열 갯수를 비교하는 방식을 썼다.

 

public int useReplace(int n) {
    int answer = n;
    int cnt = countOne(Integer.toBinaryString(n));

    while (n < Integer.MAX_VALUE) {
        int check = countOne(Integer.toBinaryString(++n));
        if (cnt == check) {
            answer = n;
            break;
        }
    }

    return answer;
}

int countOne(String str) {
    return str.replaceAll("0", "").length();
}

 

정확성 테스트에는 문제가 없었으나, 효율성 테스트를 통과하지 못했다.

 

다음은 char 로 1의 갯수를 체크했다.

 

    int countOne(String str) {
        char[] charr = str.toCharArray();
        int cnt = 0;
        for (char c : charr) {
            if (c == '1') cnt++;
        }
        return cnt;
    }

 

정확성과 효율성 모두 통과했지만..

 

Integer.bitCount 라는 메서드가 있어 훨씬 수월하게 처리가 가능하다는걸 알았다..

public int useBitCount(int n) {
    int answer = n;

    int cnt = Integer.bitCount(n);
    while (n < Integer.MAX_VALUE) {
        int check = Integer.bitCount(++n);
        if (cnt == check) {
            answer = n;
            break;
        }
    }

    return answer;
}

 

그런데 이마저도 비트 연산을 통해 더 단축할 수 있다더라... 만 비트연산은 따로 테스트해보지 않음.