https://school.programmers.co.kr/learn/courses/30/lessons/77885
양의 정수 x
에 대한 함수 f(x)
를 다음과 같이 정의합니다.
x
보다 크고 x
와 비트가 1~2개 다른 수들 중에서 제일 작은 수예를 들어,
f(2) = 3
입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.수 | 비트 | 다른 비트의 개수 |
---|---|---|
2 | 000...0010 | |
3 | 000...0011 | 1 |
수 | 비트 | 다른 비트의 개수 |
---|---|---|
7 | 000...0111 | |
8 | 000...1000 | 4 |
9 | 000...1001 | 3 |
10 | 000...1010 | 3 |
11 | 000...1011 | 2 |
정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
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을 더해서 리턴해주면 된다.
홀수인 경우에는 최하위 비트에서 가장 가까운 0
을 1
로 바꾸고, 0
바로 다음에 있는 1
을 0
으로 바꾼 수가 비트가 다른 지점이 2개 이하이면서 제일 작은 수라고 한다.
ex) 숫자가 7
인 경우 비트가 000..0111
인데 01
을 10
으로 바꾼 수인 1011
, 곧 11
이 답이 된다.