[Swift 알고리즘] 프로그래머스(Lv.2) - 점프와 순간 이동

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 점프와 순간 이동" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 점프와 순간 이동

 

---

풀이

이번 문제는 이분 탐색(?) 문제입니다.

애매하네요.

 

이번 문제의 풀이는 그라데이션으로 빠방 떠올랐습니다.

1. 2중 for문으로 처리해보자 => 최대 10억인데?

2. 1중 for문으로 dp로 처리해보자 => 최대 10억인데?

3. 절반만 반복을 돌려도 되지 않나? => 그래도 5억인데?

4. 절반씩 나눠서 계산하면 되네!

 

4단계에 걸쳐서 이 풀이가 생각이 났고 통과 후 코드를 최대한 정리했습니다.

 

이 문제는 0에서 n으로 올라가는 것이 아닌 n에서 내려가야 하는 문제입니다.

2로 나눌 수 있다는 것은 순간이동을 할 수 있다는 것이고 그렇지 않다면 건전지를 사용해 점프를 해야 합니다.

따라서 n이 짝수이면 2로 나누고, 홀수라면 1을 빼줍니다.

 

ans에는 2로 나눈 나머지를 누적합니다.

 

감사합니다!

 

---

전체 코드

import Foundation

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

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.