다음 큰 숫자_toString()으로 진수 표현

문제

문제 설명

자연수 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 이하의 자연수 입니다.

---

입출력 예

nresult

78	83
15	23

입출력 예 설명

입출력 예#1
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.

 

문제풀이

• 10진수를 2진수로 바꿔주기 위해 반복문으로 해당 값을 2로 계속 나눈 나머지 값을 임시 배열에 적재
• 조건 2인 1의 갯수를 비교해주기 위해 String.match()를 사용하여 정규표현식으로 식별 한 값만을 배열에 적재

코드

function exportOneNum(n) {
  let tmpArr = [];
  let regExp = /[1]/g;
  
  while(n) {
    tmpArr.push(n % 2);
    n = parseInt(n / 2);
  }
  let oneNum = 0;
  oneNum = tmpArr.reverse().join('').match(regExp).length;
  return oneNum;
}

function solution(n) {
  let targetNum = n;
  let target = exportOneNum(targetNum);
  
  while(targetNum) {
    targetNum++;
    let next = exportOneNum(targetNum);
    if(next === target) return targetNum;
  }
}

 

오답

몇 개의 테스트 케이스에서 시간 초과로 인해 오류 처리되었다.

 

어디서 연산 시간이 오래 걸렸을지 고민하다가, 2진수로 변환하는 과정에서 시간 복잡도가 높았을 거라는 생각에 다른 방법을 찾아보았다.

 

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Object/toString

Object.prototype.toString() - JavaScript | MDN

숫자 및 BigInts의 경우 toString()은 선택적으로 기수(radix)를 매개변수로 취합니다. 기수의 값은 최소 2부터 36까지입니다.

 

toString() 인자 값으로 기수를 넣어주면 해당 기수 값에 따른 상이한 값을 얻을 수 있음을 확인하였고 이를 이용하기로 하였다.

 

코드

function exportOneNum(n) {
  let regExp = /[1]/g;
  let binaryN = n.toString(2);  
  let oneNum = 0;
  
  oneNum = binaryN.match(regExp).length;
  return oneNum;
}

function solution(n) {
  let targetNum = n;
  let target = exportOneNum(targetNum);
  
  while(targetNum) {
    targetNum++;
    let next = exportOneNum(targetNum);
    if(next === target) return targetNum;
  }
}