프로그래머스 - Level 2. 점프와 순간 이동 / JavaScript (js)

문제설명

문제분석

 

해당 문제는 주어진 거리 N을 0에서부터 순간이동과 점프를 이용하여 이동하며, 건전지 사용량이 최소가 되도록 하는 문제입니다. 순간이동은 현재까지 이동한 거리의 2배 만큼 거리를 이동하므로, 현재 위치를 2로 나누면서 이동하면서 필요한 점프 횟수를 계산하여 건전지 사용량을 구하면 됩니다.

이를 위해 아래와 같이 접근할 수 있습니다.

1. 현재 위치를 나타내는 변수를 0으로 초기화합니다.
2. N이 0이 될 때까지 while 루프를 돌며 다음을 수행합니다.
   • 현재 위치가 짝수일 경우, 순간이동을 이용하여 이동합니다. 이때 건전지 사용량은 변하지 않습니다.
   • 현재 위치가 홀수일 경우, 점프를 이용하여 한 칸 이동합니다. 이때 건전지 사용량은 1 증가합니다.
   • 현재 위치를 2로 나눕니다.
   • 현재까지의 건전지 사용량을 반환합니다.

입력값 n이 0이될 때 까지 2진탐색하면서, n이 홀수인 경우만 카운트하는 문제입니다. 문제가 생각보다 간단해서, 바로 풀어보겠습니다.

반응형

이해하기 쉽게 코드작성하기

function solution(n) {
    let answer = 0;
    
    while(n > 0) {
    	// n이 홀수이면 1칸 앞으로 이동
        // n이 짝수이면 점프
        if(n % 2 === 1) {
            answer++;
            n -= 1;
        } else {
            n = Math.floor(n / 2);
        }
    }
    
    return answer;
}

코드 설명

n의 값이 홀수일 때 1칸씩 이동하고, n의 값이 짝수일 때에는 순간이동합니다. 이 말은 2진수로 해석하면 조금 더 깔끔하게 생각할 수 있습니다.

 

문제의 예제처럼 n이 5인 경우, 2진법으로 변환하면 101이 됩니다. 이때 1의 갯수만큼이 리턴값입니다. 이렇게되는 이유는 위의 코드로 이해할 수 있습니다. 5는 홀수이기때문에 1을 뺍니다. 10진법으로는 4가, 2진법에서는 100이됩니다. n을 절반으로 줄이면 10진법으로는 2, 2진법으로는 10이 됩니다. 마지막으로 n을 절반으로 줄이면 10진법에서는 1, 2진법에서는 1이 됩니다. 1칸은 점프할 수 없으므로 이동하면 리턴값이 2가 됩니다.

 

이렇게 되는 이유는 2진법의 특성에 기인합니다. 10진법을 2진법으로 변경할 때에는 2로 계속해서 나눕니다. 이때 나머지가 1이면 1을, 0이면 0을 기록합니다. 결국 2진법의 1의 갯수는 홀수일때만 생성되는 나머지의 갯수와 동일합니다. 따라서 이 문제처럼 n을 계속해서 2로 나누면서 n이 홀수인 경우를 카운트하는 문제는 입력값 n을 2진법으로 변환하고, 1의 갯수만 세아리는 것으로도 해결할 수 있습니다.

function solution(n) {
    return Number(n).toString(2).split("").filter(x => x === "1").length;
}