2021-12-27 / 다음 큰 숫자

문제 설명

자연수 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 = 0;
        return answer;
    }
}

 

 

정답 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        answer=n;
        
        int nCnt=0;
        String nBinary = Integer.toBinaryString(n); //10진수 -> 2진수
        
        for(int i=0;i<nBinary.length(); i++)
            if(nBinary.charAt(i) =='1')  nCnt++;
        while(true){
            answer++;
            
            int aCnt=0;
            String aBinary = Integer.toBinaryString(answer);

            for(int i=0;i<aBinary.length(); i++)
                if(aBinary.charAt(i) =='1') aCnt++;
            
            if(nCnt == aCnt) break;

        }
        return answer;
    }
}

 

 

---

 

 

조건은 총 세가지이다.

 

1) n보다 큰 수

2) 2진수로 바꿨을 때 1의 개수가 같아야 함

3)  1), 2)를 만족하는 가장 작은 수

 

첫번째 조건은 answer을 반복문에 들어가기 전 n을 대입하고 반복문에 들어가자마자 ++해주어 해결했다.

 

두번째 조건은 먼저 n의 1 개수를 찾는 것이다. 먼저 n의 2진수를 String 타입으로 구해준다. Integer.toBinaryString()을 사용한다. 그리고 1의 개수를 찾기 위해 for문을 돌려 charAt()으로 한글자씩 비교한다.

 

두 조건을 만족하기 위해 while문에서 answer를 1씩 더해준 후, 1의 개수를 구하고 n의 개수와 비교하여 만족하는 수를 구한다. 만족하지 않으면 반복문을 계속 돌린다. 

 

 

 

 

코딩테스트 연습 - 다음 큰 숫자