[Alg] Daily LeetCoding Challenge 22.03.01: 338 Counting Bits

문제: https://leetcode.com/problems/counting-bits/

0부터 n을 Binary number로 변환한 값에 속한 1의 개수를 배열로 반환하는 문제이다.문제의 난이도는 Easy로 되어있지만, Binary number에 대해 익숙하지 않다면 그닥 Easy~ 하지는 않을 수 있다. Binary number를 쭉 한번 그려보자.

내가 그린... Binary search... 너무 삐뚤빼뚤하지만... ^_^;;

n을 Binary number로 변환하면 왼쪽처럼 나올 것이고, k는 1의 개수를 의미한다. 이렇게 보니까 규칙이 한 눈에 보인다! 2의 제곱들은 1이 한 개고, 그 뒤에 있는 애들의 값들은 어떠한 규칙으로 계속 반복된다. 그리고 그 값이 조금씩 커지는데 두개씩 짝지어보면, 12, 23, 23, 34, 23, 34, 34, 45 이런 식으로 반복이 되는 것을 볼 수 있다. 사실 여기만 봤을 때 이미 알 수 있을 것이다. 12가 23을 만들어주고, 12, 23이 23, 34를 만들어주고, 12, 23, 23, 34 가 23, 34, 34, 45를 만들어주는 것이다. 

1 → 2
[1, 2]

1, 2 → 2, 3
[1, 2, 2, 3]

1, 2, 2, 3 → 2, 3, 3, 4
[1, 2, 2, 3, 2, 3, 3, 4]

1, 2, 2, 3, 2, 3, 3, 4 → 2, 3, 3, 4, 3, 4, 4, 5
[1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5]

그래서 이전에 있는 값들에 +1을 해줘서 모두 배열에 붙이면 된다! 초간단! 이대로 코드를 만들어주자.

위에서 한 설명대로 res 배열에 res에 있었던 애들은 계속 i+1 해줘서 넣으면 된다. 그리고 마지막에 반환할 때는 slicing을 해야겠지 아무래도?! 시간복잡도를 계산하자면, 대충 보기에는 O(n^2)이 나올 것 같지만, 사실 while이 돌아가는 횟수는 그렇게 높지가 않다. while문은 2, 4, 8, 16, 32...이 되는 포인트에만 수행을 하고, 그 안에 있는 반복문은 2번, 4번, 8번, 16번, 32번... 돌아가게 될 것이다. n은 100000이니까 while문은 17번 돌 것이고 그 안에 있는 값들이 모두 돈다면.... 131072번 탐색을 할 것이다. 그러니 사실상 O(n)과 다름이 없다. 

 

+) Bitwise operation을 써서 푼 사람의 코드를 봤다! 신기하니까 공유해놓겠음~

코드를 처음 보는 사람들은 읭?! 할 수도 있다. 먼저 Bitwise operation이 무엇인지 알아보고 난 다음에 본다면 한결 나아질 것이다. i >> 1을 한다는 것은 i * 1/2 를 한다는 것과 같은데, 나보다 1/2배인 애를 어따가 써먹을까? 아까 위에서 내가 찾았던 것처럼 규칙을 한번 살펴보자. 

2 >> 1과 3 >> 1은 둘 다 1이다. 하지만 2는 1을 출력, 3은 2를 출력해야 한다. 

4 >> 1, 5 >> 1 는 2지만, 4는 1, 5는 2를 출력해야 한다. 

6 >> 1, 7 >> 1은 3이지만, 6은 2를 7는 3을 출력한다. 

...

이를 반복하다 보면 눈에 보일 것이다. n >> 1이었던 값을 가져와서 n이 홀수일 때만 + 1를 해주는 것이다! i % 2는 0 또는 1만을 출력하기 때문에 4번째 줄을 저렇게 작성한 것이다. 또한 n >> 1은 사실상 n // 2와 같지만 Bitwise operation이 보다 빠르기 때문에 n >> 1을 사용했다고 한다. 😮😮👍 오오 ~~ 짱인데? 그리고 이 코드쓰니는 i % 2와 i & 1 역시 같지만, i % 2가 더 빠르다고 덧붙였다. 둘 다 같은 bitwise-operator지만 누군 더 빠르고 느리고 헷갈린다~ 나중에 기회가 되면 알아봐야지! ^-^