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

문제 링크 

프로그래머스

 

문제 유형

재귀 (Lv.2)

 

문제 풀이

• 자연수 N이 있을 때, N에서 2의 제곱인 수 중에서 N보다 작거나 같은 가장 큰 수를 뺀다.
• 이때, 2의 제곱의 지수에 해당하는 자리는 1이 된다.
• 재귀적으로 getBinaryLength 함수를 호출하여 2진수를 구하고, 2진수 중 1의 개수를 리턴한다.
• 자연수 N+1부터 반복하여 N의 2진수의 1의 개수와 같은 자연수를 찾는다.

 

코드

function solution(n) {
	// n의 최대 지수가 최대 인덱스 번호인 배열을 만든다.
	let arr = new Array(Math.floor(Math.log2(n)) + 1).fill(0); 
    const count = getBinaryLength(arr, n);
    
    let start = n + 1; // (n + 1) 부터 2진수를 구한다.
    while (true) {
        let array = new Array(Math.floor(Math.log2(n)) + 1).fill(0);
        let cnt = getBinaryLength(array, start);
        
		// n의 2진수의 1의 개수와 n보다 큰 어떤 수의 2진수의 1의 개수가 같다면 반복문 종료한다.
        if (cnt === count) { 
            break;
        }
        start++;
    }
    return start;
}

// 자연수 n의 2진수의 1의 개수를 구하는 함수
function getBinaryLength(arr, n) {
    if (n === 0) return arr.filter(v => v === 1).length;
    let num = Math.floor(Math.log2(n)); // n보다 작거나 같은 최대 (2 ** num) 값을 찾는다.
    arr[num] = 1; // 해당 지수 인덱스의 진수는 1이다.
    return getBinaryLength(arr, n - 2 ** num);
}

 

느낀 점

 

2진수 구하는 함수를 구현했는데, 알고보니 2진수는 toString()이라는 메소드로 쉽게 구할 수 있었다.

• toString() 메소드로 2진수를 구하고, 2진수의 1의 갯수를 구하는 함수만 구현하는 것이 더 성능이 좋았다.

 

10진수를 다른 진수로 변환할 때, toString()

• 특정 객체를 문자열로 변환해줄 때, 쓰이는 것이 보통이다.
• 하지만, 10진수를 다른 진수로 변환할 때도 쓰인다.
• radix: 변환할 진수, 인자로 2와 36사이의 정수가 들어간다.
• numObj.toString([radix]) 결과의 타입은 String이다.

numObj.toString([radix])

• 특정 객체를 문자열로 변환해줄 때, 쓰이는 것이 보통이다.
• 하지만, 10진수를 다른 진수로 변환할 때도 쓰인다.
• radix: 변환할 진수, 인자로 2와 36사이의 정수가 들어간다.
• numObj.toString([radix]) 결과의 타입은 String이다.

 

추가) 문자열을 특정 진수이자 정수로 변환할 때, parseInt()

parseInt(string) 
parseInt(string, radix)

• radix: string의 진수를 나타내는 2부터 36까지의 정수이다. Number 자료형이 아닌 경우 Number로 변환한다.

 

참조) toString()을 이용한 코드

function solution (n) {
  const k = count('1', n.toString(2))
  let m = n + 1

  while (count('1', m.toString(2)) !== k) {
    m++
  }

  return m
}

function count (a, bs) {
  let k = 0

  for (const b of bs) {
    if (b === a) k++
  }

  return k
}