[LeetCode] 338번 문제를 풀어보았다. (ft. java)

2022년 03월 01일 화요일 - 아우 쉬는날 너무 조아

오늘 올려볼 문제는 338번 Counting Bits 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

사실 O(n log n)에 풀었다가 Discuss보고 O(n)으로 풀었다.. ㅋㅋㅋ

입력

사진에서도 볼 수 있듯이 int 하나가 입력으로 들어온다.

---

풀이 및 코드

주어진 n까지의 수를 2진수로 봤을 때 1이 몇개씩 있는지 배열에 저장하고 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

각 index가 0이 될 때가지 2로 나누고 나머지가 1이라면 1을 더하는 식으로 구현했다.

하지만 O(n)으로 문제를 풀려고 고민하다가 하나 놓친 부분을 discuss에서 얻었다.

나는 쉬프트 연산을 하면서 2로 나누어지는 것 때문에 맨처음 비트를 계산하려 했지만 사실 맨 마지막 비트를 계산하여야 했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for(int i = 0; i <= n; i++)
            result[i] = result[i >> 1] + (i & 1);
        return result;
    }
}

---

제출 화면

사실 난 O(n log n)으로 풀었지만... 지금 올린 O(n) 풀이도 내 의지가 들어가긴 했으니... 올리겠다 ㅋㅋㅋㅋㅋ

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.