프로그래머스 - L1 기사단원의 무기

설계

약수 개수를 구할 수만 있다면, 스무스하게 풀릴거 같습니다.

소수 개수 판단법 확인했을 때, number의 제곱근만큼 확인했던 기억을 살려 활용해보자.

git : 기사단원의 무기

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

---

문제 풀이

numbers 를 순회하여 index + 1의 약수의 개수를 넣어주기

약수 개수 반환 알고리즘은 number의 제곱근만큼 반복하여 나눠줘서 나머지가 없는 경우 카운팅을 해주는데, 예를들어 16의 약수 개수를 카운팅한다고 했을때, 2 * 8 은 두 개로 카운팅되지만, 4 * 4는 하나로 카운팅해야하므로, 나눈 값과 몫을 확인해야한다!

약수 개수가 채워진 numbers를 limit 이하 만큼 필터해준 뒤, 그 합과 리밋이 넘어버린 기사의 수 * 제공되는 무기의 공격력으로 원하는 값을 반환 할 수 있다.

import Foundation
// 약수의 수가 공격력
// limit 제한
// power : 초과한 기사들의 무기 공격력
func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var numbers = Array.init(repeating: 0, count: number)
    
    numbers.indices.forEach{ index in
        numbers[index] = getCountOfDivisor(index + 1)
    }
    
    //print(numbers)
    
    let numbersCount = numbers.count
    let filteredNumbers = numbers.filter { item in
        return item <= limit
    }
    
    let sum = filteredNumbers.reduce(0, +) + (( numbersCount - filteredNumbers.count ) * power )
    
    return sum
    
}

func getCountOfDivisor(_ number: Int) -> Int {
    var count = 0
    
    let range = 1...Int(sqrt(Double(number)))
    
    for index in range {
        if(number % index == 0) {
            if(index == number / index) {
                count += 1
            }
            else {
                count += 2
            }
        }
    }
    return count
}

다른 사람 풀이 분석

프로그래머스 - LEEHAKJIN-VV 님

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var steelCount: Int = 0

    (1...number).map{ knight in
        let count = divisorCount(knight)
        steelCount += (count > limit) ? power : count
    }
    return steelCount
}

func divisorCount(_ num: Int) -> Int {
    var count: Int = 0

    for n in 1...Int(sqrt(Double(num))) {
        if num % n == 0 {
            count += 2
            if n * n == num {
                count -= 1
            }
        }
    }
    return count
}

풀이의 메커니즘은 동일하지만, 배열을 만들어주지 않고 range와 map을 활용한 방법입니다.

정리

약수 개수를 구할 때 ! 몫과 나눈 값 같을 때 카운팅 유의!

---