[Swift] 프로그래머스 기사단원의 무기(lv. 1)

[Swift] 프로그래머스 기사단원의 무기(lv. 1)

 

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

 

2. 접근

약수의 개수를 세는 로직이 가장 중요하다. number가 10만이기 때문에 O(N) 시간으로 약수를 찾으면 타임 오바가 난다.

여기서는 루트까지만 약수의 개수를 셌다. 약수를 세려고 전체를 세지 않아도 되기 때문이다. 

 

예를 들어보자면, 16의 경우

1, 2, 4, 8, 16 이렇게 약수가 존재하는데, 16을 1, 2, 3, 4으로 나눠봐도 결론이 날 수 있다.

3을 제외하고는 모두 나머지가 0이다. 그렇다면, 16의 약수로 이야기 할 수 있는 것이고, 1, 2의 경우 count를 두 번 해주면 되는 것이고, 4의 경우 count를 한 번만 해줘도 되는 것이다.

 

또 다른 예로, 8의 경우,

1, 2, 4, 8 이렇게 약수가 존재하는데, 이 때는 2루트2까지만 위와 같이 계산을 해주면 된다. 2루트 2는 근삿값으로 2.818.......뭐 이렇게 나오지 않을까. 그러면 자연수로 2까지만 계산해도 답이 나온다. 3은 할 필요가 없는 것.

 

이런 로직을 divisionCount로 구현하였고, isPrime을 두어서 소수일 경우를 조기에 걸러내어 2를 답안으로 집어넣도록 하였다.

 

길긴 긴데,,, 좋은 코드인지,, 정말 빠른 코드인지 의문이 갔다. 하지만 최대한 상수 시간에 해결할 수 있는 친구들로 메인 코드를 구성했고, 함수들을 선형 시간 안에 해결할 수 있도록 만들었기에 더 할 것은 없어보인다.

3. 코드

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var answer = [Int](repeating: 0, count: number)
    for i in 0 ... number - 1 {
        if limit == 1 {
            return number * limit
        }
        if i == 0 {
            answer[i] = 1
            continue
        }
        if isPrime(i + 1) {
            answer[i] = 2
            continue
        } else {
            answer[i] = divisionCount(i + 1, limit, power)
        }
    }
    return answer.reduce(0, +)
}

func isPrime(_ num: Int) -> Bool {
    if(num < 4) {
        return num == 1 ? false : true
    }
    for i in 2 ... Int(sqrt(Double(num))) {
        if(num % i == 0) { return false }
    }
    return true
}

func divisionCount(_ num: Int, _ limit: Int, _ maxPower: Int) -> Int {
    var count = 0
    for i in 1 ... Int(sqrt(Double(num))) {
        if num % i == 0 {
            if num / i == i {
                count += 1
            } else {
                count += 2
            }
        }
    }
    if count > limit {
        return maxPower
    } else {
        return count
    }
}