[프로그래머스] 2개 이하로 다른 비트

처리조건

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

풀이

numbers배열을 입력받고 for문으로 풀어서 각 number을 calc라는 함수로 보내서 number를 기준으로 1씩 숫자를 올리며 기준숫자인 number와 +1올린 숫자를 베타논리연산으로 비교하여 나온 값을 다시 2진수로 바꿔 각 비트를 배열로 만들어 다시 for로 풀어주면서 해당 숫자가 1인경우 number와 +1한 number의 차이로 그때마다 count를 올리다가 3이상 되면 종료해버리고 아니라면 숫자끝까지 검사해서 for문 종료와 동시에 count가 2이하이면 break하면서 현재 start를 리턴해주게 된다.

 

예를 들어 number가2고 +1한게 3이라면

둘을 베타논리연산 ^을 해주면 1이 되고 1을 2진수로 바꿔주면 01이 되며 이때 1의 갯수가 둘의 이진수에서 서로 다른값이 된다. 로직에서 베타논리연산을 해줄때 number로 들어온 기준값이 10^15승처럼 큰 수 일때 console을 찍어보면 마이너스 값이 나와버려서 BigInt를 써서 이슈를 해결했다.

function solution(numbers) {
  let result = [];
  for (const number of numbers) {
    result.push(calc(number));
  }
  return result;
}

function calc(numbers) {
  let start = numbers;
  while (true) {
    start++;
    
    let count = 0;
    let call = Number(BigInt(numbers) ^ BigInt(start))
      for (const number of call.toString(2).split("")){
        if (number==='1') count++;
        if(count>=3) break;
      }
    if (count <= 2) {
      break;
    }
  }
  return start;
}

이렇게 기존에 코드를 사용하면 기준 숫자에서 +1를 한 값을과 베타논리연산을 하여 나온 값에 또 끝까지 for문을 돌려 검사해봐야하기때문에 시간이 오래걸린다.. 그래서 테스트 10과11을 통과할 수 없다. 그래서 테스트케이스마다 기준숫자에서 조건에 맞는 숫자가 어떤 이진수 규칙을 가지는지 확인해보았다.

 

만약 기준수가 짝수라면, 예를 들어 4라면 2진수는 100이다. 여기서 진수를 바꾸는데 2이하로 바꾸며 10진수로는 5이상의 값을 찾으면 101이 될 것이다. 여기서 규칙이 있다 짝수라면 이진수끝이 0이고 여기서 1을 올린 수를 리턴하면 되므로 결론은 기준수+1이 가장 가까운 수가 될 것이다.

2 10
3 11
4 100
5 101
6 110
7 111
8 1000

 

그렇다면 홀수는 어떻게 될까 홀수는 2진수 끝에 0이아니다. 1이나올것이고 그렇다면 1과 가까운 0을 찾아서 해당 0을1로 그리고 뒤에1을0으로 바꿔주면 되므로 홀수일때는 이진수에서 뒤에서 부터 0을 찾는다. 무조건 첫번째는 홀수이니1이나올것이고 그뒤로부터 0을 찾아보면된다. 그 이유는 최하위 비트에서 멀어질 수 록 더 큰 수를 찾는데 n보다 더 크면서 가장 작은 수를 찾기 때문에 최하위 비트에서 가장 가까운 0을 변경한다.

ex: 11011(27) -> 11101(29)

 

function solution(numbers) {
    var answer = [];
    numbers.forEach((number)=>{
        let str = "0"+number.toString(2);
        const l = str.length;
        if(str[l-1] === "0"){
            answer.push(number+1);
        } else {
            for(let i = str.length; i >= 0; i--){
                if(str[i] === "0"){
                    answer.push(parseInt(str.substring(0,i)+"1"+"0"+str.substring(i+2, l),2));
                    break;
                }
            }
        }
    });
    return answer;
}