문제

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

---

입력

• 자연수 n

---

출력

n의 다음 큰 숫자를 return

---

풀이

제한조건

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
• n은 1,000,000 이하의 자연수 입니다.

접근방법

N보다 크면서 이진수로 변경하였을 때, 1의 갯수가 동일한 수를 찾는 문제이다.

1. 특정 수의 1의 갯수를 구하는 함수
특정 수의 1의 갯수를 계속하여 구하기 때문에 해당 기능을 하는 함수를 우선 작성해보자.
이진수로 변경했을 때, 1의 갯수를 세기 위하여, 수를 반드시 이진수로 변경할 필요는 없다.
bit연산을 활용하여 하나의 bit씩 확인하며 1의 갯수를 확인한다.

int getCount(int n){
	int count = 0;
	int base = 1;
	while(base < n){
		if((base & n) == base)
		count++;
		base = base << 1;
	}
	return count;
}

2. N보다 큰 수에 대하여 함수로 비교해보자.
1번에서 작성한 함수를 통해, N+1부터 1씩 증가시키며 1의 갯수를 확인해보자.

	int answer = n+1;
    int target = getCount(n);
    while(target != getCount(answer++)){}
    
    return answer-1;

---

코드

class Solution {
    public int solution(int n) {
        int answer = n+1;
        int target = getCount(n);
        while(target != getCount(answer++)){}
        
        return answer-1;
    }
    public int getCount(int n){
        int count = 0;
        int base = 1;
        while(base < n){
            if((base & n) == base)
                count++;
            base = base << 1;
        }
        return count;
    }
}