문제

https://programmers.co.kr/learn/courses/30/lessons/12911

문제 설명

자연수 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)입니다.

---

Approach #1

n보다 큼
2진수로 변환했을때 1의 개수가 같음

n을 이진수로 변환했을때 1의 개수를 셈.
n++해가면서 1의개수가 같아지면 while문 종료함.
n++숫자를 리턴.

2 78
  39 0
  19 1
  9  1
  4  1
  2  0
  1  0

Solution #1

function solution(n) {
    let nextOneCnt = 0;
    let oneCnt = convertBinary(n);
    while(nextOneCnt !== oneCnt){
        n=n+1;
        nextOneCnt = convertBinary(n);
    }
    return n;
}

function convertBinary(n){
    let oneCnt=0;
    while(n/2 !== 0){
        if(n%2 === 1) oneCnt++;
        n=parseInt(n/2);
    }
    return oneCnt;
}

N: n

Time Complexity

O(NlogN)

처음 input으로 들어오는 n을 2진수로 변환했을때 1의 개수(oneCnt)를 구할때 convertBinary함수 -> O(logN)
다음 큰 숫자를 찾기위한 solution 함수 내의 while문에서는,
n++해주면서 convertBinary함수를 또 실행하기 때문에 최종 시간복잡도는 대략적으로 O(NlogN).

Space Complexity

O(1)

Review

• convertBinary 함수에서 n/2값을 정수로 변환해주지 않아 무한루프가 됐었다. 다음엔 이런 실수 하지 않도록 유의하자...!

TIL

• parseInt(Num) -> 정수로 형변환 (ex. 3.5 -> 3)

---

Solution #2

function solution(n) {
    let oneCnt = n.toString(2).match(/1/g).length;
    while(n++){
        if(oneCnt === n.toString(2).match(/1/g).length) return n;
    }
}

Time Complexity

O(NlogN)

Space Complexity

O(1)

Review

• 프로그래머스 다른 풀이들을 참고해보니, 자바스크립트 함수 + 정규식을 이용해 효율적으로 푼 풀이가 있었다.
• 정규식 진짜 공부해야겠다... ^.^...

TIL

❗️ 자바스크립트에서 진수변환

• parseInt, toString 메소드

1) 십진수 -> 이진수
num이 십진수 12라고 가정해보자.

• num.toString(2); // "1100"

2) 이진수 -> 십진수

• parseInt("1100", 2); // "12"

❗️ 자바스크립트에서 배열 요소 중 특정 문자열만 찾는 방법

• match 메소드
• 변수.match(/찾을 문자열/g);

num = "1100"이라고 가정.
num.match(/1/g); // ['1', '1']

num.match(/1/g).length; // 2