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

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

프로그래머스

문제 풀이

1 부터 12 까지 직접 계산한 결과 규칙이 있는것을 확인했다.

• 2로 나눠지면 나눈값에 해당하는 인덱스의 값을 사용
• 나머지가 있으면 바로 이전 인덱스의 값에 +1

해당 규칙을 찾고서 DP 문제라고 생각해 코드를 작성했다.

실패한 DP 방식

결론부터 말하자면 DP 방식은 효율성 점수 0점.

다른 방식을 사용해야한다.

func solution(_ n:Int) -> Int {
    var arr = [0, 1, 1]
    guard n > 2 else { return arr[n] }

    for i in 3...n {
        if i % 2 == 0 {
            arr.append(arr[i / 2])
        }
        else {
            arr.append(arr[i-1] + 1)
        }
    }

    return arr[n]
}

아무래도 10억 이하의 자연수를 범위로 잡고 있기에, 높은 숫자를 다 체크하면서 제한시간을 초과하는것 같다.

그래서 다른 방식을 고민해봤다.

통과한 방식 (그리디? 비트 카운팅?)

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

처음부터 계산하는게 아닌 N부터 0으로 가는 스텝을 계산한 방식이다.

나머지가 있으면 한 걸음, 없으면 텔레포트 하는 방식

 

위 방식으로 효율성 점수까지 통과했다.

나누기를 최대한 활용하니까 스킵하는 스텝수가 많아져 효율성을 통과할 수 있었다.

 

그런데, 풀이를 보고나니 살짝 이상했다. 이거 비트 카운팅 할때랑 비슷한데?

그래서 몇 개 테스트케이스의 값을 이진수로 바꿔 비트가 1인 갯수만 세어보니 결과와 똑같았다..

간단한 다른 해결 방법

func solution(_ n:Int) -> Int {
    return n.nonzeroBitCount
}

결국 스위프트 내장 메서드인 nonzeroBitCount 를 써서 해결 할 수도 있었다.