[프로그래머스] 점프와 순간 이동

처리조건

https://programmers.co.kr/learn/courses/30/lessons/12980

풀이

 

우선 처리조건을 잘 이해하며 규칙성을 잘 찾아야한다. 1칸씩 이동할 때마다 1개의 배터리를 소모하고 x2씩 점프할 때는 배터리를 소모하지않으며 입력값과 정확히 같아져야한다.

 

입력값 5000을 기준으로 최소한의 건전지 사용을 구해보자

 

쉽게 생각해보면 1칸씩 이동할 때는 배터리를 소모하므로 최대한 이 1칸씩 이동하는 행위는 줄이고, 2칸씩 점프하는건 멀리이동할 수 있으면서 배터리소모가 없으니 최대한 많이 이 행위를 해야할 것이다. 그렇다면 5000을 어떻게 이 1칸이동을 최소화하고 2칸이동을 최대화할까?

 

5000을 2로 나눠가면서 홀수가 나오면 -1를 빼주며 부득이하게 1칸이동을 해주며 짝수로 바꿔주고 다시 2를 나눠가며 무한반복해주면서 0이 될 때까지 처리해주면된다.

 

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

 

또한 이진수를 통해서 풀면 더 빠르고 간단한 처리를 만들어 낼 수 있다.

 

5000을 이진형태로 바꿔주면 1001110001000으로 1이 5개다. 신기하게도 우리가 5000에서 최소 배터리 소모로 반환할 값이 5이다. 결국 5000의 2진형태에서 1인 갯수를 리턴하면 되는것이다. 그 이유는 5000다음 2500 1250 순서대로 내려가다가 625에서 2로 안나눠지고 624로 바뀌면서 625의 2진수 1001110001이 1001110000으로 되며 1이 처음으로사라진다. 앞 전에 했던 배터리소모를 1추가해주는 숫자위치랑 동일하게 된다. 점프를 2칸씩 할 수 있기 때문에 이렇게 2진형태를 이용해 구할 수 있게 된다.

 

function solution(n) {
  let answer = 0;
  n = n.toString(2).split("");
  n.filter((el) => {
    if (el === "1") {
      answer++;
    }
  });
  return answer;
}

 

이 처럼 입력값에서 1의 갯수만 찾아서 리턴하게 되면 더 빠르게 처리 할 수 있으며 코드길이는 굉장히 짧고 간단하지만 입력값을 조건에 맞게 구하기 위한 규칙성을 찾아내는 것이 힘들었던 것 같다.