[Level3]다음 큰 숫자
by EastGlow
문제
어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.
- N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
- 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.
예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다. N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.
풀이 1
class TryHelloWorld
{
public int nextBigNumber(int n)
{
int answer = 0;
int count = 0;
int count2 = 0;
String binary = Integer.toBinaryString(n);
for(int i=0; i<binary.length(); ++i){
if(binary.charAt(i) == '1') count++;
}
n++;
while(true){
String binary2 = Integer.toBinaryString(n);
for(int i=0; i<binary2.length(); ++i){
if(binary2.charAt(i) == '1') count2++;
}
if(count==count2){
answer = n;
break;
}else{
count2 = 0;
n++;
}
}
return answer;
}
public static void main(String[] args)
{
TryHelloWorld test = new TryHelloWorld();
int n = 279597;
System.out.println(test.nextBigNumber(n));
}
}
풀고나서 다른 사람들의 풀이를 보니 부끄럽다…ㅠ toBinaryString을 이용하여 2진수로 변환 후, 1의 개수를 카운트 하였다. 후에 while 문을 이용하여 n 다음의 숫자들을 같은 방식으로 카운트하여 처음 카운트한 숫자와 같으면 정답을 리턴할 수 있도록 하였다.
풀이 2
class TryHelloWorld
{
public int nextBigNumber(int n)
{
int a = Integer.bitCount(n);
int compare = n+1;
while(true) {
if(Integer.bitCount(compare)==a)
break;
compare++;
}
return compare;
}
public static void main(String[] args)
{
TryHelloWorld test = new TryHelloWorld();
int n = 78;
System.out.println(test.nextBigNumber(n));
}
}
bitCount라는 좋은 메서드가 있었다. 이것은 비트 연산을 하여 ‘1’의 개수를 리턴해준다. 코드가 반 이상 줄어버렸다.
Subscribe via RSS