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

문제 설명

문제 : [https://school.programmers.co.kr/learn/courses/30/lessons/12911]

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

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

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항

n은 1,000,000 이하의 자연수 입니다.

---

입출력 예

 

---

 

소스 코드

class Solution {
    public int solution(int n) {

        int count;
        int bitCnt = Integer.bitCount(n);

        count = checkBit(bitCnt, n + 1);
        return count;
    }

    private int checkBit(int bitCnt, int n) {
        while (n <= 1000000) {
            if (bitCnt != Integer.bitCount(n)) {
                n++;
            } else {
                break;
            }
        }
        return n;
    }
}

 

---

 

문제 해설

이진법으로 바꾼 숫자내의 1의 갯수를 세고 주어진 숫자를 계속 1을 더하여 비교하자 라는 생각을 기본으로 하여 풀어보았다.

1. Integer.bitCount()는 int n의 1의 갯수를 return하는 메서드이다.(이걸 알면 굳이 for문을 통해 1의 갯수를 셀 필요가 없다.)
2. n은 1,000,000 이하의 자연수이다. 라는 제한사항을 생각하여 while문을 통해 n의 제한을 걸어주었다.
3. 1을 추가한 n의 bitCount를 알아내고 비교한 후 같지 않다면 n을 ++하고 같다면 break해 빠져주자
4. break한 n을 return하면 완료

 

---

 

결과

딱히 효율성을 생각하지 않았는데 통과를 했다.