[Javascript] (프로그래머스 level 2) 점프와 순간이동

[Javascript] (프로그래머스 level 2) 점프와 순간이동

💡 구글에 Javascript 풀이가 많이 없거나, 배운 점이 있으면 포스팅합니다.

내 풀이

function solution(n)
{
    const dp = Array(n + 1).fill(0);
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        if (i % 2 === 0) {
            dp[i] = dp[i / 2];
        } else if (i % 2 === 1) {
            dp[i] = dp[(i - 1) / 2] + 1;
        }
    }

    return dp[n]
}

이전의 값이 다음 값을 정해줄수 있따는 생각에 DP 테이블 사용해서 풀면되겠따는 생각을 했습니다. 이렇게 풀면 답은 나오지만 유효성에서 통과를 못합니다. 그래서 나름 머리를 써본다고 아리스토텔레스의 체 처럼 걸러도 보았지만 통과를 못했습니다.

그런데 아무리 소수계산은 각 소수 계산이 O(n)이 걸리는 계산이라 O(n2)의 복잡도지만, 지금껀 단순히 2로 안나눠지면 + 1 하는 수준의 간단한 계산이라 이전 계산값을 찾을 필요가 없지 않을까? 하는 생각이 들었습니다.

두번째 풀이

function solution(n)
{
    let i = n;
    let count = 0; 
    while(i > 0) {
        if (i % 2 === 0) {
            i = i / 2
        } else if (i % 2 === 1) {
            count++;
            i = (i-1) / 2
        }
    }

    return count;
}

그래서 위 두번째 풀이처럼 n을 2로 나누다가 나머지가 생길때마다 count++을 해주는 형태로 간단하게 계산하였습니다. 이럴 경우 시간복잡도는 O(logN)이죠?

다른 사람들 풀이 참고

const solution = (n) => n.toString(2).match(/1/g).length;

그런데 다른 사람들 풀이를 보면 2로 쭉쭉 나눠준다는걸 이용해 이진수로 변경해서 1의 갯수를 센다는 아이디어가 있었습니다. 전혀 생각지도 못해서 정말 놀랬고 대단하다는 생각을 했습니다. ㅋㅋ

배운 점, 느낀 점

앞으로 저도 2로 나누는 경우 이진수를 생각하는 컴퓨터적인 사고를 좀 해야겠다고 느꼈습니다.

또한 어설프게 아는 DP 같은 것보다 훨씬 좋은 풀이가 많으니 빠르게 테케를 풀어보고 효율성체크를해서 패스가 안되면 다른 풀이로 넘어가는 방식을 채택해야겠습니다.