다음 큰 숫자

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

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

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

---

제한 사항

• n은 1,000,000 이하의 자연수 입니다.

---

입출력 예

n	result
78	83
15	23

---

풀이

function countOneInNum(num) {
  const binaryNum = num.toString(2);
  let countOne = 0;
    for(let i=0; i<binaryNum.length; i++) {
    if(binaryNum[i] === '1') {
      countOne++;
    }
  } 
  return countOne;
}

function solution(n) {
  const oneLength = countOneInNum(n);
  for(let j=n+1; j<1000000; j++) {
    if(oneLength === countOneInNum(j)) {
      return j;
      break;
    }
  }
  return j;
}

풀이 해석

주어진 수를 이진법으로 바꾸고 1의 갯수를 세는 함수 countOneInNum을 만들고,
주어진 수에 1씩 더한 것을 이진법으로 바꾼 수를 countOneInNum에 넣어 주어진 수와 1의 갯수가 같은지 비교한다.

이 외에 다른 규칙을 찾았지만, 코드로 구현하지는 않았다.

풀이와 다른 규칙
문제의 예시)
78 = 1001110
83 = 1010011
차: 5 = 101

a: 위 숫자의 bold부분, 8 -> 16 => +8
b: 위 숫자의 italic부분, 6 -> 3 => -3
+5 => 차와 같다

15 = 1111
23 = 10111
차: 8 = 1000

찾은 규칙)
먼저, 주어진 수를 이진수로 바꾸고
아랫 자리수부터 따지면서 올라가서 1이 끝나는 자리가 10이 되게 하는 수 a와
그 아랫 자리수의 1의 갯수만큼 아래서부터 자릿수를 1로 채운 수인 b를
주어진 n에 더한 값이 정답

규칙이 모든 경우에 적용되는지 확인해봄)

예1)
42 = 101010 -> 밑줄 친 1에서 1이 끝남, 밑줄 친 1이 10이 되기 위한 수 a: 2
-> 밑줄 친 1 아랫 자리수에 1이 없기 때문에 b: 0
42 + 2 + 0 = 44
정답) 44 = 101100

예2)
76 = 1001100 -> a: 8
-> 밑줄 친 1보다 아랫 자리에 1이 1개 있으므로 001이 되야함
100(십진수: 4)에서 001(십진수: 1)이 되야하므로 b: -3
76 + 8 -3 = 81
정답) 81 = 1010001

예3)
43 = 101011 -> a: 2
-> 밑줄 친 1보다 아랫 자리는 그대로이므로 b: 0
43 + 2 + 0 = 45
정답) 45 = 101101

예4)
53 = 110101 -> a: 1
-> b: 0
53 + 1 + 0 = 54
정답) 54 = 110110

예5)
13 = 1101 -> a: 8
-> 101(5)에서 011(3)이 되야하므로 b: -2
13 + 8 - 2 = 19
정답) 19 = 10011