[Swift 알고리즘] LeetCode 1387. Sort Integers by The Power Value

○ (dp ×)

Dynamic Programming, Memoization, Sorting | Medium

LeetCode 1387. Sort Integers by The Power Value

Constraints:
- 1 <= lo <= hi <= 1000
- 1 <= k <= hi - lo + 1

let solution = Solution()
print(solution.getKth(12, 15, 2)) //13
print(solution.getKth(7, 11, 4)) //7

범위가 작아서 그런지 대충 부르트 포스로 풀어도 통과는 되더라. 

medium 이면 범위 좀 크게 해서 시간초과 뜨게 해도 되지 않을까..? 싶은 문제였음. 

 

1. 완전 탐색

아무튼 단순하게 내가 푼 방식은 다음과 같다. 

lo 부터 hi 까지 반복해서 1이 나올 때까지 getPower 메서드에서 연속해서 계산을 하고 power 숫자를 더해준다.

그렇게 해서 얻은 power를 딕셔너리에 더해주고, 정렬해서 k번째 값을 반환. 

class Solution {
    func getKth(_ lo: Int, _ hi: Int, _ k: Int) -> Int {
        var dict = [Int:Int]()
        for i in lo...hi {
            dict[i] = getPower(i)
        }
        let result = dict.sorted(by: { ($0.value, $0.key) < ($1.value, $1.key) })
        
        return result[k-1].key
    }
    
    func getPower(_ x: Int) -> Int {
        var x = x
        var power = 0
        while x != 1 {
            x = (x % 2 == 0) ? x / 2 : 3 * x + 1
            power += 1
        }
        return power
    }
}

 

2. 다이나믹 프로그래밍 👍🏻

나도 문제 의도대로 DP 를 사용해서 풀고싶었는데 이게 과연 효율적인가 하는 방법들을 생각해내긴 했지만 좀 별로였고, 

아 이문제는 DP를 이렇게 사용하는거구나 하는 모범 답안은 다음과 같다. 

재귀 방식을 사용해서 getPower를 저장하고 반환하는 방식이다. 

class Solution {
    var dp: [Int:Int] = [1:0]
    
    func getKth(_ lo: Int, _ hi: Int, _ k: Int) -> Int {
        var dict = [Int:Int]()
        for i in lo...hi {
            dict[i] = getPower(i)
        }
        let result = dict.sorted(by: { ($0.value, $0.key) < ($1.value, $1.key) })

        return result[k-1].key
    }
    
    func getPower(_ x: Int) -> Int {
        if let power = dp[x] {
            return power
        }
        let power = (x % 2 == 0) ? getPower(x/2) + 1 : getPower(3 * x + 1) + 1
        dp[x] = power
        
        return power
    }
}

 

실행 속도를 비교해보니

lo - hi 의 범위가 1000이었을 때는 실행 속도가

1. 0.4811099767684937

2. 0.1762650012969971 

로 크게 차이는 없었지만, 범위를 10000으로 늘려주니 다음과 같이 큰 차이가 났다,, 

1. 5.458739995956421

2. 0.8352289199829102

범위가 늘어나도 DP 로 풀면 1초가 넘지 않더라. 멋져 ><

 

 

** 튜플은 느리다...! 

var result = [(Int,Int)]()
for i in lo...hi {
    result.append((i, getPower(i)))
}
result.sort { ($0.1, $0.0) < ($1.1, $1.0) }

return result[k-1].0

튜플을 사용해서 푼 사람들도 있길래 위와 같이

번외로 getKth 에서 딕셔너리 대신 tuple 을 사용해서 값을 저장하고 sorting 하는 작업의 실행 시간을 재 보았더니 

고작 1000인 범위에서도 실행 시간이 2.346579909324646 정도로 큰 차이가 나더라. 

tuple 쓰지 않는것으로 !