[알고리즘]프로그래머스 12911번 - 다음 큰 숫자

프로그래머스 12911번 - 다음 큰 숫자

프로그래머스 12911번 - https://programmers.co.kr/learn/courses/30/lessons/12911

 

요구사항

1.  n의 다음 큰 숫자를 반환하라.

2. n의 다음 큰 숫자의 정의는 다음과 같다.

 

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수

조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다.

조건 3. n의 다음 큰 숫자는 조건1, 2를 만족하는 수 중 가장 작은 수

 

요구사항 분석 및  풀이과정

1. n의 다음 큰 숫자는 n보다 큰 자연수이므로 탐색의 범위는 n + 1부터이다.

2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같으므로, 각각 1의 개수를 구해서 비교한다.

3. n + 1부터 순차적으로 2번을 수행하여 처음으로 1의 개수가 같은 수가 조건 1, 2를 만족하는 수 중 가장 작은 수다.

 

팁

정수 n을 2진수로 변환했을 때 1의 갯수가 필요하다면 Integer.bitCount 메서드를 이용해보자.

 

 

소스코드 작성

class Solution {
    
    public int solution(int n) {
        int base = Integer.bitCount(n);
        int start = n + 1;
        
        while(true) {
            if (Integer.bitCount(start) == base) {
                break;
            }
            start++;
        }
        
        return start;
    }
}

 

결과

 

소스코드 깃허브 주소

링크