<문제 소개>
<소스 코드>
#include <string>
#include <vector>
using namespace std;
int solution(int n)
{
// 1. n을 2진수로 변환했을 때의 1의 갯수 구하기
// 2. n+1부터 1씩 증가시켜가면서 2진수로 변환했을 때의 1의 갯수 구하기
// 3. n과 1의 갯수 비교후 같으면 해당 수를 리턴
int nCount = 0;
while(true)
{
int count = 0;
// 현재 수를 이진수로 바꿨을 때 맨 뒷자리 수부터 1인지 확인
for(int i = 0; (n>>i) > 0; i++)
{
// 시프트 연산을 이용해 나온 수가 홀수인지 판단하여 마지막 자리의 수를 확인할 수 있음.
if(((n>>i) % 2) == 1) count++;
}
if(nCount == 0) nCount = count;
else
{
if(nCount == count) return n;
}
n++;
}
}
<소스코드 2> - 비트셋 이용
#include <bitset>
using namespace std;
int solution(int n)
{
// 20개의 비트크기의 n을 담고 1의 갯수를 세준다.
int num = bitset<20>(n).count();
// n을 1씩 증가시키면서 num만큼의 1의 갯수를 가진 수를 찾는다.
while (bitset<20>(++n).count() != num);
return n;
}<풀이과정>
1. 주어진 수 n을 2진수로 바꿨을 때의 1의 갯수를 의미하는 nCount를 선언 후 0으로 초기화한다.
2. while문을 반복하면서 n부터 하나씩 증가시키면서 이진수로 바꿨을 때의 1의 갯수를 구해준다.
3. 1의 갯수를 카운팅할 count 변수를 하나 선언하고, for문을 이용해 현재 확인하는 수의 마지막 자리부터 차례로 1인지 확인한다.
4. n을 i만큼 시프트 연산을 해주면, 현재 n을 2진수로 나타냈을 때의 뒤에서부터 i번째 수를 제거한 수가 된다. 문제의 예시를 예로들자면 15(1111)를 2만큼 시프트 연산을 해주면 15>>2는 뒤부터 3(11)이 된다.
5. 따라서 n>>i 가 0보다 큰 동안만 반복을 진행해주고, 시프트 연산을 했을 때 마지막 자리가 1인지 여부는 해당 수가 짝수 홀수인지를 판단하면 쉽게 알 수 있기 때문에 시프트 연산이 된 수를 2로 나누었을 때의 나머지가 1인 경우에만 count를 증가시켜준다.
6. 위의 과정을 거치면 현재 n을 2진수로 바꾸었을 때의 1의 갯수를 파악할 수 있으므로, 이후 먼저 nCount에 아무 값도 할당되지 않은 경우는 첫번째 경우인 원래 주어진 n의 1의 갯수를 파악하는 경우이므로 이때는 nCount에 count를 대입하여 주어진 n의 1의 갯수를 넣어준다.
7. nCount가 0이 아닌 이미 n의 1의갯수가 파악이 된 경우는 nCount와 현재 count를 비교하여 같은경우를 찾고 해당 경우의 n을 리턴해준다.
8. 만약 같지 않다면 n을 증가시키고 1의 갯수가 같은 경우를 찾을 때까지 위 과정을 반복한다.
<코멘트>
나름 비트연산을 이용하여 잘 풀었다고 생각했는데 다른 사람의 풀이를 보니 비트셋?으로 푼 풀이가 있어서 해당 코드를 첨부해보았다.
<제출결과>
