Skip to main content

[Java] 12911 다음 큰 숫자

1. 문제

다음 큰 숫자

2. 정답코드

비트 조작으로 쉽게 풀 수 있는 문제이다. Integer.bitCount() 메서드를 쓰면 2진수에서 1의 개수를 쉽게 셀 수 있다.

class Solution {
    public int solution(int n) {
        int count = Integer.bitCount(n); // n의 1 개수
        int next = n + 1; 
        
        while (Integer.bitCount(next) != count) {
            next++;
        }
        
        return next;
    }
}
  1. 먼저 Integer.bitCount(n) 으로 n의 1의 개수를 구한다.
  2. n보다 큰 수부터 하나씩 증가시키면서 bitCount를 비교한다.
  3. 동일한 개수를 가지는 수를 만나면 그게 바로 답이다.

이 방식은 단순하면서도 제한 사항(최대 백만)에서도 충분히 돌아간다.

다읃 큰 수(next higher number with same number of 1-bits) 알고리즘

class Solution {
    public int solution(int n) {
        int c = n;
        int c0 = 0; // 끝의 0 개수
        int c1 = 0; // 끝의 1 개수

        // 1. n의 마지막 연속된 0 개수 세기
        while ((c & 1) == 0 && c != 0) {
            c0++;
            c >>= 1;
        }

        // 2. 그 뒤에 연속된 1 개수 세기
        while ((c & 1) == 1) {
            c1++;
            c >>= 1;
        }

        // n이 111...000 같은 형태면 더 큰 수 없음 (문제 조건에선 1,000,000 이하라 항상 있음)
        if (c0 + c1 == 31 || c0 + c1 == 0) {
            return -1;
        }

        // 3. 0 → 1로 바꿀 위치 찾기
        int p = c0 + c1; 

        // 4. 해당 비트를 1로 변경
        n |= (1 << p);

        // 5. 그 오른쪽 비트는 모두 0으로 초기화
        n &= ~((1 << p) - 1);

        // 6. 오른쪽에 (c1-1)개의 1을 채워 넣기
        n |= (1 << (c1 - 1)) - 1;

        return n;
    }
}

작동 원리

예를 들어 n = 78 (1001110)일 때:

  1. 끝에서 연속된 0 개수(c0) = 1
    (...10 → 끝의 0 하나)
  2. 2. 그 앞에서 연속된 1 개수(c1) = 3
    (...1110 → 111)
  3. p = c0 + c1 = 4
    즉, 오른쪽에서 4번째 비트를 0→1로 바꿔야 함.
  4. 그 뒤의 비트들을 0으로 초기화한 뒤,
  5. 가장 작은 수를 만들기 위해 맨 오른쪽에 (c1-1)개의 1을 배치한다.

결과: 1010011 (83)



Back to top