약수의 합

약수의 합

문제 설명

• 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

제한 사항

• n은 0 이상 3000이하인 정수입니다.

 

문제 풀이

for 반복문을 이용하여 1부터 n까지 반복하면서 n을 반복문의 반복 변수의 값으로 나누어서 나머지가 0일 경우 배열에 변수 값을 추가하고, 그 배열의 값을 모두 더하면 풀 수 있을 것 같았다.

잘 될 것이라는 생각과 달리 17번의 테스트중 한 번 에러가 났다. 생각해보니 n이 0부터 3000까지의 정수인데 0일 경우 반복문 범위가 1에서 0까지라 에러가 난 것일 것이다.

func solution(_ n:Int) -> Int {
    guard n > 0 else { return 0 }
    var divisor: [Int] = []
    for i in 1...n {
        if n % i == 0 {
            divisor.append(i)
        }
    }
    return divisor.reduce(0, +)
}

따라서 guard문으로 n이 0일 경우 0을 반환하도록 걸러내었다.

더 나은 방법 생각하기

이렇게 하면 문제는 풀리는데, 생각을 좀 더 해보면 약수를 찾기 위해 1에서 n까지 반복하는 방법이 숫자가 작을땐 괜찮지만 숫자가 커질수록 반복을 매우 많이 하게 되어 비효율적이게 된다.

예시로 solution(123456780)을 실행하면 4분에 가까운 시간이 걸린다..

약수를 생각해보면, 12의 약수는 [1, 2, 3, 4, 6, 12], 100의 약수는 [1, 2, 4, 5, 10, 20, 25, 50, 100] 이런 식인데, 가운데를 기준으로 양 옆의 숫자를 곱하면 원래 수가 나온다. 즉 모든 약수 중 절반만 구하면 나머지 약수는 원래의 수를 구한 약수로 나누면 되는 것이다.

그럼 그 가운데를 어떻게 나눌까? 제곱근으로 하면 간단하다. 12의 경우 3.46... 이기 때문에 3 이하의 약수만 구하면 되고, 100의 경우 10이기 때문에 10 이하의 약수만 구하면 된다.

제곱근으로 나눌 때 위의 100의 경우처럼 제곱근이 정수로 맞아 떨어지면 중복이 생기게 되므로 그 부분을 없애기 위해 배열로 선언했던 것을 Set으로 선언하였다. 순서는 엉키게 되겠지만 합만 구하면 되니 상관 없을 것이다.

func solution(_ n:Int) -> Int {
    guard n > 0 else { return 0 }
    var divisor: Set<Int> = [] // 중복을 받지 않기 위해 Set으로 설정
    
    for i in 1...Int(sqrt(Double(n))) { // sqrt는 Double로 입력을 받고 결과도 Double이라 형변환을 두번 해줘야한다
        if n % i == 0 {
            divisor.insert(i)
            divisor.insert(n/i)
        }
    }
    return divisor.reduce(0, +)
}

 

sqrt를 통해 제곱근을 구하긴 했는데 제곱근이다 보니 Double타입의 입력이 필요했는다. 여기서 다루는 타입은 전부 Int이기 때문에 입력 n을 Double로 형변환 한 뒤, 반환된 제곱근을 다시 Int로 형변환 해야 했다.

이렇게 해서 위에 입력했던 큰 숫자인 1234567890을 다시 입력해서 테스트 해보았는데,

소요 시간이 약 200초가 넘게 걸리던 것에 비해 약 0.02초로 매우 크게 단축 되었다.

다른 사람은 어떻게 풀었나..?

다른 사람들이 제출한 알고리즘을 확인해 보는 것도 새로운 시각을 제공해줘서 공부할 때 한 번씩 해보는 것도 꽤 괜찮은 방법인 것 같다. 제출 풀이를 쭉 살펴보니 약수를 모두 구한뒤 마지막에 reduce만 쓴 나와 달리 filter를 통해 반복문을 쓰지 않고도 약수를 구하고, filter뒤에 reducee도 바로 붙여서, return 한 줄로 약수와 합을 모두 구하는 사람들이 꽤 많았다.

또 새로운 것도 알게 되었는데 Array(1...n)의 형식으로 1부터 n까지 숫자가 들어간 배열을 생성하는 방법도 있었다..

Array(1...n).filter{n % $0 == 0}.reduce(0, +)로 작성해 내가 처음에 작성한 코드를 한 줄로 줄여버렸다. 물론 내가 테스트 해본 대로 이렇게 하면 1부터 n까지 검토하므로 숫자가 크면 매우 오래걸리겠지만, 코드 자체는 한줄로 작성 가능해 매우 간결해 보였다.

이 범위를 sqrt를 사용해 줄이면 한 줄로도 내가 작성한 두번째 코드가 아마 가능할 것이다. 고차함수의 사용법에 대해 좀 더 익숙해질 필요가 있겠다.