[ 프로그래머스 JAVA ] 다음 큰 숫자

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12911

프로그래머스

걸린 시간

08:40 ~ 09:34 // 소요 시간 54분

피드백

잘 풀었는데 테스트 케이스 1개 때문에 시간을 많이 소비했음.

반복문에서 비교하는 값 중에 고정 값이 있으면 고정 시키고 값 비교

Integer.bitCount( int value ) 이런 함수 쓰면 더 효울적인 것 같긴 한데 

저런 함수 알고 쓰는 사람이 몇이나 될까.. 싶은 ?

 

문제

자연수 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)입니다.

소스 코드 ( 자세한 내용 주석 참고 )

class Solution {
    public int solution(int n ) { 
        int answer = n+1;
        
        // n의 다음 큰 숫자는 
        // 1. n 보다 큰 자연수 <- for 문을 n+1 부터 실행
        // 2. n을 2진수로 변환 했을 때 1의 갯수가 같음. <- n 의 1의 개수 == next 의 1의 개수 
        // 3. 조건 1 , 2 를 만족 하는 수 중 가장 작은 수  <- for문으로 돌려서 제일 먼저 나온 수 채택
        // n 값은 고정 값이기 때문에 미리 고정
        String nBinary = Integer.toBinaryString(n);
        
        // 이진 변환 했을 때의 1의 개수 저장하는 변수
        int nOneCnt = nBinary.length() - nBinary.replace("1" , "").length();
        int nextOneCnt = 0;
        
        // 반복문 들어가기전 1이 한개인 숫자들 우선 체크 
        // 1,000,000 이하 중 제일 큰 2의 n제곱의 수는 20이다. 
        // 2의 21승 만큼 while 문이 돌아가야하기 때문에 2의 k승과 n 이 같을경우 2의 k+1 을 다음 큰수로 반환
        // int 는 2의 31승 만큼이 최대 값임
        for( int i = 0 ; i <= 31 ; i ++ ){
            // 1의 개수가 1개인 케이스 
            if( n == Math.pow( 2 , i ) ){
                return (int) Math.pow( 2 , i + 1 );
            }
            
            if( n < Math.pow( 2 , i ) ) break;
        }
        
        
        // 위 1,2,3 조건이 만족하면 break 로 탈출~
        while(true){
            
            // 예비 다음수에 대한 이진수 String 저장
            String ansBinary = Integer.toBinaryString(answer);
            // 예비 다음수의 이진수 1의 개수 저장
            nextOneCnt = ansBinary.length() - ansBinary.replace("1" , "").length();
            
            // 조건 2가 만족될 경우 다음 큰 숫자 확정
            if( nOneCnt == nextOneCnt ){
                break;
            }
            
            // 아닐 경우 +1 하여 확인
            answer++;
        }
        
        
        return answer;
    }
}