다음 큰 숫자 - Integer.bitCount()의 발견

문제 이름 및 링크

다음 큰 숫자

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

 

출제 사이트

프로그래머스

 

문제유형 및 난이도

문제유형: 기초

난이도: Level2

 

코드 설명

기존에 생각했던 방식의 코드는 아래와 같습니다.

class Solution {
    public int solution(int n) {
        String nBinary = Integer.toBinaryString(n);
        int oneCount = countOneInBinaryString(nBinary);
        while(true) {
            n++;
            String newNBinary = Integer.toBinaryString(n);
            if(oneCount == countOneInBinaryString(nBinary)) return n;
        }
    }
    private int countOneInBinaryString(String str) {
        return str.length() - str.replace("1","").length();
    }
}

주어진 숫자를 Integer.toBinaryString으로 이진법 형태로 변형한 뒤, 1의 개수를 셉니다.

n보다 큰 숫자 중 주어진 숫자와 1의 개수가 같은 최소값을 찾기 위해 1씩 증가시키며 이진법 형태로 변형한 뒤 1의 개수를 세 같은지 확인합니다.

 

문제의 풀이에는 문제가 없었으며 정확도 검사는 통과했습니다.

다만 효율성 검사에서 문제가 발생했습니다.

 

생각해보니 컴퓨터는 값을 이진법 형태로 기억하고 있을 수 밖에 없습니다.

그러면 이진 비트에서 1의 개수를 세는 연산이 존재할거라 생각했습니다.

그 연산의 메서드가 Integer.bitCount() 였습니다.

 

Integer.bitCount를 사용한 코드는 아래와 같습니다.

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

 

변형된 코드에서 확인할 수 있듯이 이전 코드는 일을 두 번하게 만드는 코드였습니다.

코드의 본질을 까먹지 말고 활용할 수 있도록 성장하면 좋겠다는 생각이 든 문제였습니다.