[Algorithm] 다음 큰 숫자

'다음 큰 숫자' 정의는 다음과 같다.

 

자연수 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 x = n;
        int nCount= 0;
        
        while (true) {
            String strBin = Integer.toBinaryString(x);
            int xCount = 0;
            int fromIndex = -1;
            while ((fromIndex = strBin.indexOf("1", fromIndex + 1)) >= 0) {
                xCount++;
            }
            if (x == n) {
                nCount = xCount;
            }
            else {
                if (nCount == xCount) {
                    return x;
                }
            }
            x++;
        }
    }
}

1. 정수값을 스트링형 바이너리로 변환한다. 

2. 스트링의 각 인덱스에 해당하는 값이 "1"인지 확인하여 카운트한다.

3. 입력 받은 값 n을 바이너리로 변환했을 때 1의 개수와 같은지 확인한다.

4. 위 내용을 입력 받은 값부터 1씩 증가하여 (3)의 조건이 맞을 때까지 무한 반복한다.

 

Feedback

1. 조건 없이 왜 무한루프를 돌아야 하는가?

 

2. indexOf 없이 length만큼 전체를 확인해서 "1"을 찾는 것과 비교하여 어떤 것이 더 가벼운 작업일지?

 

3. 카운트만 하면 되는데 x == n 작업을 해야 하는지?

 

 

피드백을 반영하여 다음과 같이 새로 작성했다.

class Solution {
    public int solution(int n) {
        int x = n + 1;
        int nCount = getBinaryOneCount(n);
        
        while (nCount != getBinaryOneCount(x)) {
            x++;
        }
        
        return x;
    }
    
    private int getBinaryOneCount(int num) {
        String strBin = Integer.toBinaryString(num);
        int len = strBin.length();
        int count = 0;
        
        for (int i = 0; i < len; i++) {
            if ('1' == strBin.charAt(i)) {
                count++;
            }
        }
        
        return count;
    }
}

1. 조건 없이 왜 무한루프를 돌아야 하는가?

값을 찾을 때까지 반복으로 수정한다.

 

2. indexOf 없이 length만큼 전체를 확인해서 "1"을 찾는 것과 비교하여 어떤 것이 더 가벼운 작업일지?

length만큼 반복하여 charAt()을 이용하여 문자를 비교한다.

 

3. 카운트만 하면 되는데 x == n 작업을 해야 하는지?

카운트 값만 비교하기 위해 메소드를 따로 만들어 사용한다. [getBinaryOneCount()]

 

 

타 스터디원의 다른 방법도 소개한다.

    private int getBinaryOneCount(int num) {
        int count = 0;
        
        while (num != 0) {
            count += num % 2;
            num /= 2;
        }
        
        return count;
    }

정수값 num을 2로 나누었을 때 나머지 값을 더하고, num을 2로 나눈다.

위 과정을 num이 0이 아닐 경우 반복한다.

흔히 우리가 2진수를 구하는 로직이다.

 

비트 연산자를 이용하는 방법도 따로 공부해봤다.

    private int getBinaryOneCount(int num) {
        int count = 0;
        
        while (num != 0) {
            num &= (num - 1);
            count++;
        }
        
        return count;
    }

n & (n-1)를 하면 LSB에서 가장 가까운 1만 사라지게 된다. 입력 값이 0이 아닐 때까지 반복 및 카운트한다.

처음에는 이해가 안 됐으나, 직접 눈으로 확인하고 반복 학습하여 이해했다.

 

link : https://kylog.tistory.com/6

2진수 표현에서 1의 개수 세기