문제
풀이
1. 이진수로 변환해서 풀기
처음에는 정수를 string 타입의 이진수로 변환하는 함수를 만들어서 풀었습니다.
다음은 정수를 string 이진수로 변환하는 함수입니다.
1
2
3
4
5
6
7
8
9
10
11
// 정수 n을 이진수로 변환
string getBinary(int n)
{
string ret="";
while(n>0){
int remain = n%2;
n/=2;
ret = to_string(remain)+ret;
}
return ret;
}
n을 1씩 증가시키며 위의 getBinary로 변환해주고 1의 개수가 같을 경우에 값을 return해줬습니다.
이렇게 풀어도 다음과 같이 통과가 되지만 더 효율적인 방법이 있습니다.
2. 비트마스크로 풀기
비트마스크에 대해서는 이 포스팅에서 간단히 설명해놓았습니다.
다음의 함수는 비트마스크를 사용해 정수 n의 이진수의 1의 개수를 반환합니다.
1
2
3
4
5
6
7
8
9
int countOne(int n){
int ret=0;
// n의 이진수에서 1의 개수 세기
for(int i=0 ; i < 31 ; i++){
if(n & 0x01<<i)
ret++;
}
return ret;
}
n & 0x01«i 는 이진수 n의 자리마다 1을 검사하는 코드입니다.
위처럼 굳이 string으로 변환하지 않아도 바로 이진수의 1의 개수를 계산할 수 있습니다.
다음은 비트마스크로 풀이한 결과입니다.
비트마스크 풀이가 더 빠른 속도를 보이는 것을 확인할 수 있습니다.
String 변환 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <string>
#include <vector>
#include <iostream>
using namespace std;
// 정수 n을 이진수로 변환
string getBinary(int n)
{
string ret="";
while(n>0){
int remain = n%2;
n/=2;
ret = to_string(remain)+ret;
}
return ret;
}
// 이진수에서 1의 개수를 세기
int countOne(string &s){
int ret=0;
for(int i=0;i<s.length();i++){
if(s[i]=='1')
ret++;
}
return ret;
}
int solution(int n) {
int answer = 0;
string start = getBinary(n);
int one = countOne(start);
for(int i=n+1;;i++){
string binary = getBinary(i);
if(one==countOne(binary)){
answer=i;
break;
}
}
return answer;
}
비트 마스크 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <string>
#include <vector>
using namespace std;
int countOne(int n){
int ret=0;
// n의 이진수에서 1의 개수 세기
for(int i=0 ; i < 31 ; i++){
if(n & 0x01<<i)
ret++;
}
return ret;
}
int solution(int n) {
int standard = countOne(n);
while(1){
n++;
if(standard == countOne(n))
return n;
}
}
