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

[68] 점프와 순간 이동

책 구매하기

문제 정보

• 분류: 시뮬레이션
• 정답률: 68%
• 권장 시간 복잡도: O(log N)
• 핵심 키워드: 비트, 홀수 카운트, 순간 이동, 그리디
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12980

문제를 읽을 때 체크할 포인트

순간 이동은 비용이 0이고, 점프만 배터리를 쓴다. 결국 가장 적게 점프하려면 가능한 한 많이 2로 나누면 되고, 남는 비용은 이진수에서 1의 개수와 같다.

규칙을 그대로 따라가는 문제처럼 보여도 상태를 어떻게 단순하게 들고 갈지가 더 중요하다. 좌표나 값의 변화만 깔끔하게 관리하면 의외로 짧게 끝난다.

풀이 흐름

1. n이 0이 될 때까지 반복한다.
2. 짝수면 2로 나누고, 홀수면 1을 빼면서 배터리 사용량을 1 늘린다.
3. 누적된 사용량을 반환한다.

구현할 때 놓치기 쉬운 부분

순간 이동은 배터리를 쓰지 않고 점프만 배터리를 쓴다. 결국 몇 번 점프해야 하는지를 세는 문제이며, 그 수는 2진수에서 1의 개수와 이어진다.

파이썬 정답 코드

def solution(n):
  # n이 0이 될 때까지 반복한다.
  answer = 0
  # 짝수면 2로 나누고, 홀수면 1을 빼면서 배터리 사용량을 1 늘린다.
  while n:
    # 누적된 사용량을 반환한다.
    if n % 2 == 1:
      answer += 1
      n -= 1
    else:
      n //= 2
  return answer

시간 복잡도

N은 목표 위치 n이다.

반복 한 번이 끝날 때마다 대상 크기가 절반 가까이 줄어드는 구조이다. 그래서 전체 반복 횟수는 N이 아니라 라운드 수에 해당하는 log N만큼만 필요한다.

따라서 시간 복잡도는 O(log N)이다.