[프로그래머스] 다음 큰 숫자

문제 설명

자연수 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을 2진수로 변환 후 1의 개수를 카운트한 변수를 선언하고 반복문을 이용하여 1의 개수가 같지 않으면 n값을 1씩 증가시키는 방법으로 풀이하였다.

2진수로 변환 후 1의 개수를 구하는 과정은 함수를 따로 만들었다.

function solution(n) {
    // 자연수 n의 2진수 변환 후 1의 갯수 카운트
    const oneCount = binaryConversion(n);
    // 반복문을 이용하여 2진수 변환하여 1의 개수가 같은 값일 경우 리턴
    while (binaryConversion(n + 1) !== oneCount) n++;
    
    return n + 1;
}

function binaryConversion(n) {
    return n.toString(2).split("").filter(str => str === "1").length;
}

다른 풀이를 보다보니 굳이 split, filter를 쓰지않고 정규식을 이용하여 match함수를 사용하는 방법도 있다는걸 알게됬다.

function binaryConversion(n) {
    return n.toString(2).match(/1/g).length;
}

 

시간 복잡도는 O(k * n)이며, 여기서 k는 n의 이진 표현에서 자릿수다. 이는 binaryConversion 함수의 시간 복잡도가 O(k)이고 while 루프가 binaryConversion 함수를 호출할 때마다 최대 n번 실행되기 때문.
공간 복잡도는 O(k)다. 왜냐하면 binaryConversion 함수는 n의 이진 표현을 보유하기 위해 k 길이의 배열을 만든 다음 match 함수를 사용하여 1을 찾기 때문.

 

다른풀이 - 1

프로그래머스 다른 풀이 중 재귀 함수를 응용한 방법이다.

function solution(n,a=n+1) {
    return n.toString(2).match(/1/g).length == a.toString(2).match(/1/g).length ? a : solution(n,a+1);
}

 

다른풀이 - 2

Chat GPT가 추천해준 방법.

function solution(n) {
    // 1의 갯수를 카운트 하는 숫자 변수 초기화
    let oneCount = 0;
    // n을 2진수 변환
    let binary = n.toString(2);
    
    // for문 - 1의 개수 카운트
    for (let i = 0; i < binary.length; i++) {
        if (binary[i] === "1") oneCount++;
    }
    
    // while문 - n의 값을 1씩 증가시키면서 1의 갯수를 카운트
    while (true) {
        n++;
        let count = 0;
        binary = n.toString(2);
        
        for (let i = 0; i < binary.length; i++) {
            if (binary[i] === "1") count++;
        }
        
        // 맨 처음 1의 갯수가 같다면 증가된 n을 리턴
        if (count === oneCount) return n;
    }
}