프로그래머스 다음 큰 숫자 JAVA 풀이 (비트 연산, Integer.bitCount)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

자연수 n이 주어질 때 다음 조건을 만족하는 가장 작은 자연수를 구하는 문제이다.

• n보다 큰 수
• n과 2진수의 1의 개수가 같은 수
• 조건을 만족하는 수 중 가장 작은 수

예를 들어 78의 이진수는 다음과 같다.

78 = 1001110

1의 개수는 4개이다.

이후 숫자를 확인하면

79 = 1001111 (5개)
80 = 1010000 (2개)
81 = 1010001 (3개)
82 = 1010010 (3개)
83 = 1010011 (4개)

따라서 정답은 83이다.

---

📌 접근 방법

현재 숫자의 1의 개수를 먼저 구한다.

int count = Integer.bitCount(n);

그 후 n + 1부터 탐색하면서 같은 개수의 1을 가지는 숫자를 찾는다.

while (true) {
    n++;

    if (count == Integer.bitCount(n)) {
        return n;
    }
}

조건을 만족하는 가장 첫 번째 숫자가 곧 정답이다.

---

📌 핵심 아이디어

1. Integer.bitCount() 활용

2진수로 변환하지 않아도 내부적으로 1의 개수를 계산해준다.

Integer.bitCount(78);
// 4

---

2. 현재 숫자의 1 개수 저장

기준이 되는 1의 개수를 저장한다.

int count = Integer.bitCount(n);
78 = 1001110
// 1의 개수 = 4

---

3. 다음 숫자부터 탐색

현재 숫자보다 큰 수만 확인해야 하므로 먼저 증가시킨다.

n++;

---

4. 1의 개수 비교

현재 숫자의 1 개수가 기준 개수와 같다면 정답이다.

 

if (count == Integer.bitCount(n))

예시

83 = 1010011
↓
1의 개수 = 4
↓
78과 동일

---

📌 전체 코드

class Solution {
    public int solution(int n) {

        int count = Integer.bitCount(n);

        while (true) {
            n++;

            if (count == Integer.bitCount(n)) {
                return n;
            }
        }
    }
}

 

---

📄 정리

• 문제의 핵심은 숫자의 크기가 아니라 2진수에서 1의 개수이다.
• Integer.bitCount()를 사용하면 1의 개수를 쉽게 구할 수 있다.
• n + 1부터 순차 탐색하여 조건을 만족하는 첫 번째 숫자를 찾는다.
• 비트 연산 관련 문제에서 자주 활용되는 자바 내장 메서드를 익힐 수 있다.