프로그래머스 - 점프와 순간 이동(Swift)

프로그래머스 - 점프와 순간 이동(Swift)

 

 

 문제 설명

 

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

프로그래머스

 

 나의 풀이

 

어디선가 풀어 본 유형이지만 결국 풀지못해서 다른 사람의 풀이를 봤다.

숫자의 범위가 10억이니 for문도 dp문제도 아닌 것을 빨리 알고 이 문제는 절반씩 없애는 문제라는 걸 직감했어야 했다.

 

n을 거꾸로 감소시키면서 진행되는데 n이 홀수일때는 1을 빼주고 짝수일때는 순간이동(2로 나누는 것)을 해주면 된다.

 

앞에서 부터 탐색해서 n까지 어떤 규칙으로 순간이동을 해야할까 고민하고 있었는데 뒤에서 부터 탐색하니 홀수는 무언가를 2배해서 올 수 있는 숫자가 아니라는 걸 알게 됐다. 

 

import Foundation

func solution(_ n:Int) -> Int 
{
    var ans: Int = 0
    var a = n
    
    while a > 0 {
        ans += a % 2
        a = (a % 2 == 0) ? a / 2 : a-1
    }

    return ans
}

 

 

 피드백

 

ans += a % 2를 통해서 홀수만 1을 빼준 것을 담을 수 있게 된다.

문제를 거꾸로 생각하는 능력과 숫자의 범위가 클 때 이분탐색 문제임을 빠르게 인지하는 능력이 필요하다.