[코딩 테스트 RUN] PROGRAMMERS LV 2 : 다음 큰 숫자

 

⚠️ 주의!
프로그래머스에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

[LV 2] 연습문제 : 다음 큰 숫자

프로그래머스

 

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

 

문제 해설

이 문제의 핵심 포인트는 01을 10으로 바꾼다는 지점이다. 무슨 소리냐면, 이진법은 0 or 1로 이루어져 있다. 01에서 넘어가면 다음 단위가 1이 되며, 따라서 10이 된다는 것이다. 1111이라는 이진수가 있으면, 다음으로 큰 숫자는 10000이다. 본 문제의 조건인 1의 갯수가 같다는 지점이 여기서 중요해진다.

 

예를 들어 1의 갯수가 1개라고 쳐보자, 100보다 큰 이진수는 101, 110, 111이 있다. 문제는 셋 다 1의 갯수가 맞지 않는다. 2개라고 쳐보면, 1001이라고 치면 1010이 되지만, 1100이라고 치면 10001이어야 하게 된다. 즉, 핵심은 뒤에서부터 세어서 제일 도달하는 01을 10으로 바꾸는 것이다. 이후 1은 그 이후에 1의 개수에 따라서 채워두면 된다. 이에 따라 방법은 다양하게 풀 수 있는데, 나는 두 가지 방법으로 풀었다. 첫 번째는 위의 방식을 그대로 배열 형태로 두어 처리하는 것이다. 두 번째는 바로 비트연산인데, 정답 코드를 하나하나 같이 보는 것이 해설에 도움이 될 거 같아서 이번에는 두 방식 다 별도 해설을 넣겠다.

 

첫 번째: 배열로 01을 10으로 바꾼다.

정말 많은 방법으로 시도했던 방법이다. 처음 설계는 사실 이 방법이 아니라 다른 설계를 사용했는데, 계속 보고 있다보니 생각난 게 바로 이 배열로 01을 10으로 바꾸는 방법이다. 나의 경우 조금 더 안전하고 복잡한 식으로 했는데, 인덱스가 헷갈릴 수 있으니 주의하자.

 

        int twoMath = 0;
        for (int i = 0; i < 20; i++) {
            twoMath = (int) Math.pow(2, i);
            if (n < twoMath) {
                break;
            }
        }

 

일단 숫자 n보다 큰 2의 제곱수를 구했다. 배열 1~~~을 사용하기 위해서다.

 

        String b = Integer.toBinaryString(n);
        String b2 = Integer.toBinaryString(twoMath);
        char[] nBinary = new char[b2.length()];
        Arrays.fill(nBinary, '0'); 

        int start = nBinary.length - b.length();
        for (int i = 0; i < b.length(); i++) {
            nBinary[start + i] = b.charAt(i);
        }

        char[] binary = Arrays.copyOf(nBinary, nBinary.length);

 

그리고 둘을 toBinaryString으로 만들어 String으로 저장한다. nBinary라는 char 배열을 만들었는데(후에 toString을 사용하여야 하므로 char배열로 해두는 걸 추천한다), 이 사이즈가 중요하다. 바로 twoMath의 길이만큼으로 설정한 것. 왜냐하면 자리수를 넘어가는 경우가 존재하기 때문이다. 이후 Arrays.fill로 이걸 0으로 채워줬다.

 

그리고 nBinary.length - b.length()를 해두었는데, 시작점을 잡아 거기부터 n의 수로 채우기 위해서다. 그러므로 toCharArray()의 사용은 어려운 상태이다. 그리고 큰 수를 찾기 위한 배열 binary를 만들어 nBinary를 복사한다. 처음에는 이 복사를 행하지 않았더니 오류가 나서 의아했는데, 처음에는 10000과 같은 수로 만들어 여기에 1을 추가하는 방식으로 했기 때문이다. 이 경우 1의 개수를 맞추기도 어렵고, 그렇게 되면 10100과 같은 수는 대응을 못하므로, 복사 처리를 해줘야 한다. 원본에서 수정하지 않는 이유는, 원본은 그대로 두는 것이 이후 할 1의 개수의 카운트 등을 위해서다.

 

        int idx = -1;

        for (int i = nBinary.length - 1; i >= 1; i--) {
            if (nBinary[i] == '1' && nBinary[i - 1] == '0') {
                binary[i - 1] = '1';
                idx = i;
                break;
            }
        }

 

그리고 바로 이게 01을 10으로 만드는 작업이다. 거꾸로 세어야 한다는 게 핵심. 그리고 i - 1을 사용해야 하기 때문에 i는 최소 1이어야 한다. 자신의 앞이 바로 0인 1일 경우, 해당 0을 1로 만들고 위치를 저장한다. idx를 저장하는 이유는 이후 공정 때문이다.

 

        if (idx != -1) {
            binary[idx] = '0';

            int countOne = 0;
            for (int i = idx + 1; i < nBinary.length; i++) {
                binary[i] = '0';
                if (nBinary[i] == '1') countOne++;
            }

            for (int i = binary.length - 1; i > idx && countOne > 0; i--) {
                binary[i] = '1';
                countOne--;
            }
        }

 

-1일 경우가 존재할 수도 있으므로 (10000 등) 이 경우는 논외로 친다. 따라서 idx가 -1이 아닐 경우, idx를 0으로 두고, idx 이후부터도 0으로 둔다. 그리고 여기서 1의 개수를 센다. 이렇게 센 것을 토대로 끝부분 부터 다시 1을 채워나가면 된다.

 

마지막으로 char을 String으로 만들고 Integer.parseInt로 2진수->10진수로 바꿔주면 된다.

 

return Integer.parseInt(new String(binary), 2);

 

 

두 번째: 비트연산

뒤 늦게 떠올린 비트 연산. 어차피 이진수라면 비트연산 쪽이 훨씬 빠르고 좋다.

 

        int c = n;
        int c0 = 0; 
        int c1 = 0;

 

먼저 n을 c라는 변수로 저장했다. 원본을 유지하고, c에 비트 연산을 하기 위해서다. 그리고 c0은 0의 개수, c1은 1의 개수를 위한 부분이다.

 

        while (((c & 1) == 0) && (c != 0)) {
            c0++;
            c >>= 1;
        }

        while ((c & 1) == 1) {
            c1++;
            c >>= 1;
        }

 

먼저 0의 개수를 세고, 이어서 1의 개수를 센다. 여기서 (c & 1) == 0 은 가장 오른쪽에 있는 비트가 0인지 확인한다. 그리고 0이라면 0의 개수를 추가한다.  c＞＞=1 은 c를 오른쪽으로 한 칸 밀어서 다음 비트를 검사할 준비를 하겠단 뜻이다. 1의 경우도 같은 형태로 개수를 센다.

 

        int p = c0 + c1;
        n |= (1 << p);
        n &= ~((1 << p) - 1);
        n |= (1 << (c1 - 1)) - 1;
        return n;

 

int p = c0 + c1; 로 가장 낮은 01 패턴에서 0이 1로 바뀔 자리의 인덱스를 지정한다. 위에서 했던 idx와 비슷한 역할이다. 그리고 다음 줄에서 p번째 자리의 0을 1로 바꾼다. 여기서 |= 는 OR 연산으로, 두 비트 중 하나라도 1이면 결과가 1이 되는데, 여기에 1＜＜p 를 사용하여 1을 p 자리만큼 밀어낸다(p번째 자리를 1로 채운다). 그리고 &= 는 AND 연산으로, 두 비트 중 하나라도 0이면 결과는 0이 된다. 그리고 ~((1＜＜p) - 1)  를 사용하는데, p번째 미만의 모든 자리를 1로 만든단 의미(-1)지만, ~이라는 NOT 연산을 사용하여 반대로 0으로 만든다. 위에서 사용했던 10후 아래에 모든 수를 0으로 만드는 것과 동일하다. 마지막으로는 결과 1을 c1 - 1의 개수만큼에 1을 채운다는 의미이다. c1 - 1인 이유는, 위에 p번째에서 1을 지정했기 때문.

 

이 방식을 패턴화해서 압축한 방식이 바로 가장 많이 좋아요를 받은 정답이다.

 

 

사용하지 않은 세 번째 방식: bitCount

실질적으로는 bitCount가 가장 기억하고 쉽고 헷갈리지 않기 때문에, bitCount 방식이 많이 권장된다. bitCount는 해당 숫자 내부에(이진수로 봤을 때의) 1의 개수를 세는 메서드다. 1의 개수가 여기서 가장 중요하기 때문에 사용하는 것인데, 여기서는 다음과 같은 방식으로 사용할 수 이싿.

 

class Solution {
    public int solution(int n) {

    int count = Integer.bitCount(n);
    while (Integer.bitCount(++n) != count);
    return n;        
        
    }
}

 

n의 bitCount를 센다, 그리고 while문으로 bitCount가 count와 개수가 맞을 때까지 n을 가산하는 것이다. 1씩 늘리는 무식한 방법이지만, bitCount는 빠른 속도로 연산하므로 연산 속도에 문제는 없다.