[Swift 알고리즘] LeetCode 2457. Minimum Addition to Make Integer Beautiful

×

그리디? Medium

You are given two positive integers n and target.
An integer is considered beautiful if the sum of its digits is less than or equal to target.
Return the minimum non-negative integer x such that n + x is beautiful. The input will be generated such that it is always possible to make n beautiful.

Constraints:
- 1 <= n <= 10^12
- 1 <= target <= 150
- The input will be generated such that it is always possible to make n beautiful.

class Solution {
    func makeIntegerBeautiful(_ n: Int, _ target: Int) -> Int {
        //code
    }
}

출력 예시

print(solution.makeIntegerBeautiful(16, 6)) //6
print(solution.makeIntegerBeautiful(467, 6)) //33
print(solution.makeIntegerBeautiful(1, 1)) //0

 

결국 풀긴 했지만 시간이 너무 오래 걸려서 틀린걸로,, ㅠ

첫단추를 잘못 꿰서 아쉽쓰

몬가 앞자리수 부터 확인하는게 더 빠르게찌..? 생각했는데 지옥같은 예외처리들로 결국 실패,, 

그냥 뒤에서부터 정직하게 더해주는 게 가장 예외없이 정확하게 푸는 방법인걸로 ,,

 

1차 시도 : 당연히 통과 안될 줄 알았지만 그냥 무식하게 계속 1씩 더해봄 - 실패 (Output Limit Exceed)

class Solution {
    func makeIntegerBeautiful(_ n: Int, _ target: Int) -> Int {
        var n = n
        var x = 0
        var sum = target + 1
        while sum > target {
            sum = 0
            for i in String(n) {
                sum += Int(String(i))!
            }
            x += 1
            n += 1
        }
        return x - 1
    }
}

 

2차 시도 : 앞자리수부터 자릿수 더해가면서 합이 target 보다 크면 반올림하고 뒤에 다 0으로 바꿔주기 - 실패

반올림하면 자릿수가 늘어날 때, 9일 때 반올림 처리 등 예외처리 해줘야하는 부분이 너무 많아서 극혐이었음,, 앞자리부터 금지.. ㅠ 

 

3차 시도 : 앞자리 포기하고 뒷자리부터 하긴 했는데 여기서도 반올림 버리지 못하고 뻘짓하다가 예외처리 실패.. 

 

4차 시도 : 드디어 통과 Runtime 5 ms / Memory 14 MB

순수하고 정직하게 뒷자리부터 차근차근 더해주기.. ㅎ 

1. sum : 각 자릿수 더해주기

2. sum 이 target 보다 클 경우, 맨 뒷자리수부터 반올림 하기 위해 더해줘야 하는 temp 구하기

3. 초기 입력 값 n 에서 temp 를 더해준 후, 각 자릿수의 합을 구하고 sum 이 target 보다 작거나 같을 때까지 반복.

4. sum 이 target 보다 작거나 같아지면, 구해준 beautiful 정수에서 초기 입력값 n 을 뺀 수 x 를 반환   

class Solution {
    func makeIntegerBeautiful(_ n: Int, _ target: Int) -> Int {
        var array = String(n).map({ Int(String($0))! })
        var sum = array.reduce(0, +)
        var beautiful = n
        for i in 0..<array.count {
            var zero = 1
            if sum > target {
                for _ in 0..<i {
                    zero *= 10
                }
                let temp = (10 - array[array.count - 1 - i]) * zero
                beautiful += temp
                array = String(beautiful).map({ Int(String($0))! })
                sum = array.reduce(0, +)
            } else {
                break
            }
        }
        
        return beautiful - n
    }
}

 

 

---

LeetCode 써본 적 있나..? 처음 써보는 건가? 기억은 안나는데 오 좋다!

문제도 깔끔하고 무엇보다 어떤 test case에서 오류가 났는지 알려주니까 너무 좋더라 ㅎㅎ