문제

첫 번재 풀이 (실패)

로직

먼저 n을 binary로 바꾼 값에서 1의 개수를 구한다. (해당하는 개수를 count1OfN이라고 한다.)
그 후에 n+1부터 숫자를 1을 더하는 것을 반복한다. (해당 숫자를 checkNum이라고 정의한다.)
반복문 안에서는 checkNum을 binary로 바꾼 값이 countOfN과 동일한지 확인한다.
만약 동일하다면 checkNum을 반환한다.
동일하지 않다면 반복문을 계속 수행한다.

코드

class Solution {
    public int solution(int n) {
        Long count1OfN = count1(n);
        int checkNum = n;
        
        while (true) {
            checkNum += 1;
            Long count1OfCheckNum = count1(checkNum);
            
            if (count1OfCheckNum == count1OfN) {
                return checkNum;
            }
        }
    }
    
    // 이진수에서 1의 개수 구하는 함수
    private Long count1 (int n) {
        String binary = Integer.toBinaryString(n);
        
        return binary.chars().filter(c -> c == '1').count();
    }
}

결과

모든 수를 비교하는 방식은 정확성에서는 만점을 받았지만 효율성에서는 모든 문제가 시간 초과로 0점을 받았다.

2번째 풀이

로직

1번째 풀이를 통해 얻은 것은 모든 숫자를 이진수로 변환하고 체크하여 시간이 오래 걸린다고 생가하여 이진수를 이용하는 다른 로직들을 정리하고 풀어보았다.
계속 시간 초과 혹은 정확도에서 틀리는 경우가 발생하였다.

그래서 어떤 함수가 있을까 찾아보던 중 Integer의 내장 메서드인 bitCount라는 메서드를 발견하였다!
해당 메서드는 10진수 숫자의 이진수에서의 1의 개수를 세어주는 함수이다.
예를 들어, Integer.bitCount(78)을 입력하면 4가 출력이 된다.
78의 이진수는 1001110이고 여기서 1의 개수는 4이기 때문이다.

나는 이 함수를 이용하여 매우 간단하게 이 문제를 해결하였다.

코드

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

결과

새롭게 알게된 점

이 문제를 통해 bitCount라는 메서드의 존재를 알게 되었다.
결국 함수를 이용하여 풀게 되었지만 푸는 과정에서 다양한 로직을 도전해볼 수 있는 좋은 기회였다.