[Swift 알고리즘] 백준 2231 분해합

백준 2231번 <분해합>

브루트 포스 예제 2단계

 

 

1차시도 : 69100KB / 296ms

아무런 조건 없이 그냥 1부터 다 검사하는 걸로 해도 시간은 오래걸리지만 통과는 되더라. 

func minGenerator(_ n: Int) -> Int {
    for i in 1...n {
        var sum = i
        for j in String(i) {
            sum += Int(String(j))!
        }
        if sum == n {
            return i
        }
    }
    return 0
}

 

2차시도 : 69100KB / 8ms

1부터 다 체크하는 건 비효율적이기 때문에 조건을 달아주었다. 

입력 숫자가 256일 경우, 각 자리 수의 최대 합은 2 + 9 + 9 = 20 이 된다고 생각했다. 

그러면 256의 생성자는 최소 256 - 20 = 236 이상이 될 수 밖에 없다. 

따라서 입력 숫자의 첫번째 자리 수 + 나머지 자리는 9씩 더해주어 분해합에서 뺀 수에서부터 체크하도록 조건을 달아주었다. 

func minGenerator(_ n: Int) -> Int {
    let tmp = Int(String(String(n).first!))! + 9 * (String(n).count - 1)
    for i in n-tmp..<n {
        var sum = i
        for j in String(i) {
            sum += Int(String(j))!
        }
        if sum == n {
            return i
        }
    }
    return 0
}

 

 

근데 사실 다른 사람들 코드 참고해보니까 굳이 첫째자리 수까지 구해서 할 필요는 없는거같더라. 

그냥 n - n의 자리수 x 9 만 해줘도 시간상에 큰 차이는 없었다. 그치,, 더 해봐야 최대 8개 더 검사하는건데 딱히 차이는 없겠지.. ㅋㅋㅋ

for i in n-String(n).count*9..<n { ... }

심지어는 주어질 수 있는 n의 최대값이 1,000,000 인 걸 생각하여 자릿수 합의 최대 경우의 수를 6 x 9 = 54 로 잡고 고정값으로 두어 다음과 같이 푼 사람도 시간은 8ms 로 같았다. 

for i in max(1, n - 54)...n { ... }

 

이해하기 쉽진 않지만 이런 답안도 있더라. 

let n = Int(readLine()!)!
var answer = 0
for i in max(1, n - 54)...n {
    if n == i + String(i).reduce(0, { $0 + Int(String($1))! }) {
        answer = i
        break
    }
}
print(answer)

더 축약하면 이렇게 되는듯,, 어렵다,,

let N = Int(readLine()!)!, M = max(1,N-54)
print((M...N).first(where:{$0+String($0).reduce(0){$0 + Int(String($1))!} == N}) ?? 0)