다음 큰 숫자

작성일: 2024-10-16

문제 링크 : 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 이하의 자연수 입니다.

입출력 예

n result
78 83
15 23

입출력 예 설명

입출력 예#1
문제 예시와 같습니다.

입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.

접근 방식

  1. 먼저 주어진 숫자를 2진수로 변환했을 때의 1의 갯수를 알아낸다.
  2. 주어진 숫자에서 1을 더해가며, 주어진 수자와 1의 갯수가 같은 숫자를 찾아낸다.
  3. 결과를 리턴한다.

결과

소스 코드 

class Solution {
    public int solution(int n) {
        int answer = 0;
        String origin = Integer.toBinaryString(n).replace("0","");
        int cnt = 0;
        while(true){
            cnt++;
            if (origin.length() == Integer.toBinaryString(n+cnt).replace("0", "").length()){
                answer = n+cnt;
                break;
            }
        }

        return answer;
    }
}
  • 주어진 숫자를 2진수로 변환하고, 0을 제거한다.
  • while문을 돌면서, 주어진 숫자에 1을 더한다 -> 2진수로 변환 -> 0제거 -> 주어진 숫자와 길이 비교 -> 같은 경우 break

결과 이미지

alt text

다른 접근 방식

Integer의 bitCount() 라는 메소드를 이용한 코드가 있었다.

int number = Integer.bitCount(3); // 2

그래서 코드의 길이가 많이 줄었다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int origin = Integer.bitCount(n);
        int cnt = 0;
        while(true){
            cnt++;
            if (origin == Integer.bitCount(n+cnt)){
                answer = n+cnt;
                break;
            }
        }

        return answer;
    }
}

알게 된 점

bitCount() 이라는 메소드에 대해 알게 되었다.

해당 메소드를 사용하면, 주어진 숫자를 2진수로 변환했을 때의 1의 개수에 대해 알 수 있다.