다음 큰 숫자

문제

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같은 조건을 만족합니다.

1. n의 다음 큰 숫자는 n보다 큰 자연수입니다.
2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수입니다.

• 입력: 자연수 n (1 ≤ n ≤ 1,000,000)
• 출력: n의 다음 큰 숫자

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

풀이 1: 2진수 문자열 변환을 이용한 직관적 탐색

작성해주신 코드와 같이, 숫자를 2진수 문자열로 변환하여 '1'의 개수를 직접 세는 방법입니다.

• 1의 개수 카운팅: Integer.toBinaryString()을 이용해 주어진 숫자 n을 2진수 형태의 문자열로 변환합니다. toCharArray()로 문자 배열을 순회하며 '1'의 개수(cnt)를 셉니다.
• 다음 숫자 탐색: 정답 후보인 ans를 n + 1부터 시작하여 1씩 증가시킵니다.
• 조건 비교: 각 ans마다 동일하게 2진수 문자열로 변환하여 '1'의 개수(cnt2)를 세고, 원본 n의 1의 개수(cnt)와 일치하는 순간 반복문을 종료(break)하고 반환합니다.

코드 1

class Solution {
    public int solution(int n) {
        int cnt = 0;
        // n의 2진수 내 1의 개수 카운트
        for (char c : Integer.toBinaryString(n).toCharArray()) {
            if (c == '1') {
                cnt++;
            }
        }
        
        int ans = n + 1;
        while (true) {
            int cnt2 = 0;
            // ans의 2진수 내 1의 개수 카운트
            for (char c : Integer.toBinaryString(ans).toCharArray()) {
                if (c == '1') {
                    cnt2++;
                }
            }
            
            // 1의 개수가 같으면 탐색 종료
            if (cnt == cnt2) {
                break;
            }
            
            ans++;
        }
        
        return ans;
    }
}

풀이 2: Integer.bitCount() 내장 함수를 활용한 최적화

자바에는 정수의 2진수 표현에서 '1'의 개수를 O(1) 수준으로 매우 빠르게 세어주는 내장 함수인 Integer.bitCount()가 존재합니다. 이를 활용하면 문자열 변환 객체 생성과 반복문 없이 단 몇 줄만으로 속도와 가독성을 극적으로 향상시킬 수 있습니다.

• 탐색 숫자 ans를 1씩 증가시키는 로직은 동일하지만, 1의 개수를 비교하는 과정을 단 한 줄의 조건문으로 처리하여 오버헤드를 최소화합니다.

코드 2

class Solution {
    public int solution(int n) {
        // n의 2진수 1의 개수를 내장 함수로 한 번에 구함
        int cnt = Integer.bitCount(n);
        
        int ans = n + 1;
        
        // ans를 1씩 증가시키며 bitCount 값이 같은 것을 찾음
        while (true) {
            if (cnt == Integer.bitCount(ans)) {
                break;
            }
            ans++;
        }
        
        return ans;
    }
}

알고리즘 분류

수학 (Mathematics), 비트 조작 (Bit Manipulation), 완전 탐색 (Brute Force)