문제
🎶 DJ욱제는 비트에 몸을 맡기는 중이다. 🎶
DJ욱제는 비트에 심취한 나머지, 비트를 비틀어 제껴버리는 문제를 내 버렸다!
N자리 이진수 K가 주어진다. K가 0이 아닐 때까지 아래의 연산을 적용했을 때, 연산이 일어나는 횟수를 구하시오.
K = K-(K&((~K)+1))
아래는 위의 연산에 사용된 연산자에 대한 설명이다.
'+'는 산술 더하기 연산이다. (5 + 2 = 7)
'-'는 산술 빼기 연산이다. (5 - 2 = 3)
'&'는 비트 AND 연산이다. (1101 & 0111 = 0101)
'~'는 비트 NOT 연산이다. 켜진 비트를 끄고, 꺼진 비트를 켜는 연산이다. (~1101 = 0010)
1 ≤ N ≤ 1,000,000
입력
첫째 줄에 N이 주어진다.
둘째 줄에 N자리 이진수 K가 주어진다. K는 0으로 시작하지 않는다. 즉, leading zero는 없다.
출력
연산이 일어나는 횟수를 출력한다.
예제 입력
5
10110
예제 출력
3
내가 했던 풀이 방법
- K = K-(K&((~K)+1))과 while을 이용해 0이 될 때까지 반복 -> 실패
- K = K-(K&((~K)+1)) 식의 의미를 해석 후 풀이 -> 성공
너무 어렵게만 생각해서 처음에는 복잡했는데, 단순하게 의미만 생각해보면 구하고자 하는 것이 무엇인지를 파악할 수 있음.
- ~k : not 연산(0과 1을 바꿔줌)
- (~k)+1 : 이진수에 1을 더해줌. 이때, 더해지는 수가 1일 경우 올림처리 되어 상위비트에게 영향을 주게 될 수 있다. 이 영향은 더해지는 수가 0일 때까지 지속된다. 즉, 2번 연산을 통해 하위비트에서부터 처음으로 0이 등장하는 구간을 1로 바꾸고 그 이하의 비트들은 0으로 바꿔준다.
- k&((~k)+1) : ~k는 k와 모든 수가 다르기 때문에 모두 0을 반환하겠지만, 2번 연산을 통해 하위비트에서 처음으로 0이 등장한 자리만 1을 반환하게 된다. 왜냐하면, 기존에 1이었던 게 ~k를 통해 0이 됐으나, 2번 연산을 통해 1이 됐기 때문에 기존과 현재가 모두 1로 같기 때문에.
- K-(K&((~K)+1)) : 3번 연산을 통해 (~k)의 하위비트에서 처음으로 0이 등장하는 자리만 1이 되었으므로, 해당 연산을 통해 해당 비트(하위비트에서 처음으로 0이 나오는 곳)를 1에서 0으로 바꿔주게 된다. 이를 k를 기준으로 설명하면, k의 하위비트에서 처음으로 1이 등장하는 자리를 0으로 바꿔준다.
즉, 처음 입력받은 이진수에서 1의 개수를 출력하면 된다.
코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let N = parseInt(input[0]);
let binary = input[1];
let answer = 0;
for (let i = 0; i < N; i++) {
if (binary.charAt(i) === '1') {
answer++;
}
}
console.log(answer);
회고
해당 식을 단순히 적어서 풀이하는 게 정답일거라고 생각해서는 안 됐는데... 조금 더 문제가 의도하는 게 무엇일까를 생각해보는 게 필요할 것 같다. 항상 빠르게 구현하고자 하는 것 같아서 효율성이 떨어지는 코드들로 자주 구현하는 것 같다.
비트 마스킹 문제를 처음? 접해본건가?? 비트마스킹 문제를 풀어봐야 할 것 같다는 생각이 크게 들었던 문제였다. 문제에서 의도한 식도 나름 유명한 식이라고 하니... 배움이 부족하다는 걸 느꼈다. 문제를 많이 푸는 것도 좋지만 제대로 알고 풀도록 해보자.
