99클럽 코테 스터디 17일차 TIL(6월 6일) + 알고리즘 DP(Dynamic Programing,동적계획법)

[문제 링크]

https://leetcode.com/problems/counting-bits/description/

 

[문제 사고]

주어진 정수의 길이를 가지며 0부터 시작인 오름차순 배열을 만든 후 각 요소를 순회하며 주어진 조건에 맞는 배열로 연산하여 반환한다.

 

[문제 해결]

1. n의 길이를 가지며 0부터 시작하는 오름차순 배열을 생성한다.
2. 배열을 map method로 순회하며 각 요소들을 이진법으로 변환하며 이중 배열을 생성한다.
3. 이진법으로 변환한 각 요소들을 한글자씩 분리하며 문자열 형태로 만든다.
4. 문자열로 분리된 요소들을 reduce method를 이용해 숫자로 변환하며 각 요소들의 합을 구한다.
5. 각 요소들의 합이 들어있는 새로운 배열을 반환한다.

 

[작성 코드]

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    const arr = Array(n+1).fill(1).map((e,i) => e = i);
    const newArr = arr.map(e => e.toString(2).split('').reduce((a,b) => Number(a) + Number(b),0));
    return newArr
};

 

[문제 회고]

문제에 접근하는 방법과 문제를 풀어내는데에는 어려움이 전혀 없었다. 하지만 불필요한 변수 선언으로 인한 메모리 할당과 다양한 메서드의 사용으로 인해 런타임이 상대적으로 길게 나오는 경향이 있다. 동적 계획법 알고리즘을 공부하며 본 문제의 효율성을 높이고 메모리 사용량을 줄일 수 있는 방법을 생각해봐야겠다.