[Programmers] 점프와 순간이동


  • Programmers의 점프와 순간이동 문제 풀이입니다

  • 문제의 조건을 보면 숫자 N이 1이상 10억 이하의 자연수이기 때문에 0번째 칸부터 도차갛는 지점까지 모든 경우를 고려하는 것은 불가능하다

  • 따라서 규칙을 발견해야 하는데, 도착 지점에서 0번째 칸으로 역으로 이동하는 경우를 보면 다음과 같은 규칙성을 발견할 수 있다

  • 짝수칸에서는 2를 나눈 칸으로 순간이동해서 이동하고

  • 홀수칸에서는 점프해서 1칸 이동하는 것을 알 수 있다

  • 따라서 N이 5000일 때 다음과 같은 과정을 거쳐 0번째 칸으로 이동한다

  • 5000 -> 2500 -> 1250 -> 675 -> 674(-1) => 387 -> 386(-1) -> 193 -> 192(-1) -> 96 -> 48 -> 24 -> 12 -> 6 -> 3 -> 2(-1) ->1 -> 0(-1)

  • 총 5번의 점프를 한 것을 확인할 수 있다


전체코드

function solution(n) {
  let count = 0;
  while (n > 0) {
    console.log('n: ', n);
    if (n % 2 == 0) n = n / 2;
    else {
      n -= 1;
      count += 1;
    }
  }
  return count;
}

Reference









© 2020. by dkmqflx

Powered by dkmqflx