[Leetcode 아주 상세한 문제풀이] 338. Counting Bits – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 338번 문제 Counting Bits 이다.

우선 문제를 살펴보자.

 

리트코드 338번 문제 Counting Bits (링크)

Counting Bits - LeetCode

Counting Bits - LeetCode

 

 

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

 

 

문제 설명

문제에 대해 간략히 살펴보자. 인풋으로 정수 n이 주어지고 그 인풋에 대해 길이가 n+1인 배열을 리턴해야 한다. 이때 리턴해야 하는 배열의 인덱스는 0부터 n까지 매치된다. 이때 매치되는 정수를 2진수로 표현했을 때 1의 개수를 그 배열의 element로 리턴해야 한다는 것이다. 문제가 조금 헷갈릴 수 있으니 예를 들어보자.

문제 예시 1번을 보면 n=2로 주어졌다. 따라서 리턴해야 하는 배열의 길이는 3 (=n+1)이다. 이때 배열의 각 인덱스는 숫자 0, 1, 2와 매치된다. 이 숫자들을 2진수로 표현하면 0, 1, 10이 된다. 따라서 각 2진수의 1의 개수는 0, 1, 1개이다. 따라서 문제에서 요구하는대로 2진수로 변환했을 때의 1의 개수인 [0, 1, 1]을 리턴하면 된다.

이제 문제를 한 번 풀어보자.

 

 

문제 접근법

이 문제는 파이썬에서 제공하는 built-in 함수를 이용해 쉽게 해결할 수 있다.

기본적인 아이디어는 인풋으로 주어진 n에 대하여 0부터 n까지 숫자를 2진수로 표현해 1의 개수를 세어보는 것이다.

파이썬에서는 bin()이라는 내장 함수를 제공한다.

이 함수는 숫자를 2진수로 변환하며 이때 변환된 2진수는 문자열 (string)이다.

또한 count method를 이용하여 2진수로 변환된 문자열에서 1의 개수를 파악할 수 있다.

예를 들어 count('1')이라고 하면 문자열에서 '1'이 몇번이나 나타나는지 계산할 수 있다.

따라서 문제에서 요구하는 바로 대로 '1'이 몇번이나 나타나는지 계산 후 인덱스 순서대로 리스트에 업데이트 하면 우리가 구하고자 하는 답을 찾을 수 있다.

이제 코드로 한 번 알아보자.

 

 

문제 풀이

정수 n을 입력받기 위한 함수를 정의해 준다. (line 1)

'1'의 개수를 저장할 빈 리스트도 하나 만들어 준다. (line 2)

우리는 이제 0부터 n+1까지 for loop를 이용하여 하나하나 탐색할 것이다. (line 4)

앞서 설명한대로 bin()이라는 내장 함수를 이용하여 주어진 숫자를 2진수로 변환한다. (line 6)

그 후 변환된 2진수 문자열에서 '1'이 몇개나 존재하는지 count 함수를 이용하여 계산한다. (line 6)

이때 계산된 '1'의 개수를 변수에 담아둔다.

우리는 0부터 차례대로 첫번째 인덱스에 매칭하면 된다.

따라서 '1'의 개수 계산 결과를 차례대로 결과 리스트에 업데이트 해준다. (line 6)

이 과정을 0부터 n까지 모든 정수에 대해 마치고 나면 최종적으로 결과 리스트 (ans)을 리턴하고 종료한다. (line 7)

 

 

문제 풀이 코드

def countBits(n):
    ans = []
    for i in range(n + 1):
        # Convert number to binary and count the number of 1's
        count_ones = bin(i).count('1')
        ans.append(count_ones)
    return ans
 
# Example usage
print(countBits(2))  # Output: [0, 1, 1]
print(countBits(5))  # Output: [0, 1, 1, 2, 1, 2]