⭐ Lv. 2 - 다음 큰 숫자
✅ 문제 설명
자연수 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 |
입출력 예#1
- 문제 예시와 같습니다.
입출력 예#2
- 15(1111)의 다음 큰 숫자는 23(10111)입니다.
✅ 풀이 코드 + 설명
첫 풀이는 간단한 방식으로 해결하였습니다. 우선 처음으로 주어진 n의 이진수 표현 시의 1의 개수를 변수에 저장합니다. 이후 loop를 돌며 n을 1씩 증가시켜 가장 처음으로 n의 1의 개수와 동일하게 된 숫자를 return합니다.
function solution(n) {
let countOne = [...n.toString(2)].filter((v) => v === '1').length;
while(n++) {
if([...n.toString(2)].filter((v) => v === '1').length === countOne) return n;
}
}이와는 다른 신기한 풀이법을 발견해 추가로 작성합니다. 우선 재귀와 정규표현식을 활용한 방식입니다. match를 활용하여 1의 개수를 판단함과 동시에, 이를 재귀 함수로 표현하여 코드를 간결하게 작성할 수 있습니다.
function solution(n, cur = n + 1) {
return n.toString(2).match(/1/g).length === cur.toString(2).match(/1/g).length ? cur : solution(n, cur + 1);
}다른 한 가지 방법은 비트 연산자를 활용한 방법입니다. 해당 코드는 아직 이해를 하지 못해 출처와 코드를 아래 남깁니다.
// programmers NiceHwang님의 코드
/* 개인 저장용
** 알고리즘 시간 복잡도 O(log n) 이지만 사실상 O(a)에 가까움.
** 655395 입력후 1억번 실행에 소요 시간450ms 미만 */
function nextBigNumber(n) {
var i, j;
for (i = 0; !(n & 1); i++) {n = n >> 1; } // 1을 찾을때까지 우로 쉬프트, 쉬프트 횟수 = i
for (j = 0; n & 1; i++, j++) {n = n >> 1; } // 0을 찾을때까지 우로 쉬프트, 1의 갯수 = j
for (j--, n++; i !== j; i--) {n = n << 1; } // 0자리에 1대입, 1의 갯수 -1, i === j 가 될때까지 죄로 쉬프트하면서 쉬프트 횟수 -1
for (i; i; i--, n++) {n = n << 1; } // i === 0 될때까지 좌로 쉬프트 하면서 쉬프트 횟수 -1, 0자리에 1대입
return n;
}
festina lenta