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

박먼지·2023년 1월 7일
0

코딩테스트

목록 보기
13/23
post-thumbnail

💡 문제

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

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

  • x보다 크고 x비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

  • f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
비트다른 비트의 개수
2000...0010
3000...00111
  • f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
비트다른 비트의 개수
7000...0111
8000...10004
9000...10013
10000...10103
11000...10112

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

  • 1 ≤ numbers의 길이 ≤ 100,000
  • 0 ≤ numbers의 모든 수 ≤ 1015

내 풀이 📝

function solution(numbers) {
  var temp = "";
  return numbers.map((v)=>{
     if (v%2===0) return v+1; // 짝수일 때는 뒤가 0으로 끝나기 때문에 1만 더해주면 됨!
     else{
        temp = "0" + v.toString(2);
        for(let i = temp.length-1; i >= 0; i--){
            if(temp[i]==="0"){
              return parseInt(temp.substring(0,i) + 
                              "10" +
                              temp.substring(i+2,temp.length),2);
            }
        }
     }
  });
}

처음에는 숫자를 1씩 더해서 비트연산자 ^ (비트가 다를 경우 1 return)를 사용해서 1의 개수가 2개 이하인 경우에 return 하는 식으로 구했더니 테스트 케이스 10,11번에서 실패하였다.

찾아보니까 비트연산자가 32비트 이상이 되면 그냥 32비트 정수로 변환이 된다고 한다.

Before: 11100110111110100000000000000110000000000001;
After: 10100000000000000110000000000001;

아무튼 큰 수에는 비트 연산자를 쓸 수 없다는 걸 깨닫고.. 또 찾아보는데..

짝수인 경우 2진수로 변환 했을 때 마지막이 0으로 끝나기 때문에 1만 더해주면 다른 비트의 개수가 1개가 되므로 1을 더해서 리턴해주면 된다.

홀수인 경우에는 최하위 비트에서 가장 가까운 01로 바꾸고, 0바로 다음에 있는 10으로 바꾼 수가 비트가 다른 지점이 2개 이하이면서 제일 작은 수라고 한다.

ex) 숫자가 7인 경우 비트가 000..0111인데 0110으로 바꾼 수인 1011, 곧 11이 답이 된다.

profile
개발괴발

0개의 댓글