프로그래머스 - 다음 큰 숫자

⭐ 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;
}

---