99클럽(2기) - 코테스터디 10일차 TIL # Dynamic Programming

LeetCode - 338. Counting Bits

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.

• 정수 n이 주어졌을 때, n + 1 길이의 array ans반환
• ans의 요소는 0부터 n까지의 10진수를 2진수로 변환했을 때의 1의 개수

---

 

풀이

1) 0부터 n까지의 정수로 이루어진 리스트 생성

 리스트 컴프리핸션으로 0부터 n까지의 수를 리스트로 만들었다. 

• 리스트 Comprehension 사용법
  • [표현식 for 요소 in 이터러블]

 

2) 해당 리스트의 모든 요소를 바이너리로 변환

 map 함수로 0부터 n까지의 정수에 대해 bin 함수를 이용해서 바이너리로 변환했다. bin함수의 반환값은 '0bxxx..'이므로 앞의 0b는 제외하고 3번째 요소부터 마지막 요소까지 사용하기 위해 bin 함수의 반환값에 [2:]로 범위를 지정해줬다.

• map 함수 사용법
  • map(이터러블 각 요소에 적용할 함수, 이터러블)
    • 이터러블 각 요소에 적용할 함수는 lambda 함수로 표현 (lambda 인자들: 표현식)
    • lambda 이외에도 int, str 등의 파이썬 내장 함수, 사용자 정의 함수 등을 map의 파라미터로 전달할 수 있음  
      • 예1) a = [1, 2, 3], map(lambda x: x **2, a) → list(a) = [1, 4, 9]
      • 예2) a = ['1', '2', '3'], map(int, a) → list(a) = [1, 2, 3]
    • map 함수의 반환값은 맵 객체로, 그 결과를 확인해보면 <map at 0x79336ec271f0>와 같음. 맵 객체에는 지연 평가(lazy evaluation)가 적용되어 이터레이션을 할 때만 요소를 계산하기 때문에 모든 계산이 적용된 결과값을 한 번에 확인하려면 list 함수나 tuple함수를 적용해줘야 함

 

3) 바이너리로 변환된 요소에서 1의 개수를 세서 반환 

 역시 map 함수에 "count 함수를 사용해 '1'의 개수를 세는 lambda 함수"를 전달해 각 요소의 1의 개수를 센 수를 리스트로 만든 후 해당 리스트를 반환한다.

def count_bits(self, n: int):
    nums = [i for i in range(n + 1)]        
    binaries = map(lambda x: bin(x)[2:], nums)
    answer = list(map(lambda x: x.count('1'), binaries))
    return answer

 

 

다른 사람의 풀이

 아.. 굳이 0부터 n까지의 리스트를 만들 필요도, map 함수를 적용해 해당 리스트의 요소들을 바이너리로 만든 후 3번째 스트링부터 저장할 필요도 없었다. 어짜피 '1'을 세는 것이 중요하기 때문에 0부터 n까지 순회하며 바이너리로 만든 후 1을 센 값을 ans에 추가해주기만 하면 됐었다. 

def count_bits(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

 

느낀점

 불필요한 연산을 생략하고 복잡한 문제를 단순화하는 연습이 더 필요하다. 그래도 오늘 문제는 비교적 쉽게 느껴졌다. 이런 날도 있어야지~