[swift] 프로그래머스 - 기사단원의 무기

프로그래머스

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

문제 설명

 

각각의 기사는 기사 번호(number)를 가지고 있고

number의 약수는 기사의 공격력을 의미합니다.

기사의 공격력을 구하고

공격력이 limit을 넘는다면 power로 공격력이 고정됩니다.

기사단 전체의 공격력의 합을 구하면 되는 문제입니다.

 

해당 문제의 구현은 쉽지만

시간제한을 해결해야 하는 풀이입니다.

 

---

 

시간초과 풀이(오답 코드)

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var result = [Int]()
    for i in 1...number {
        result.append(0)
        for j in 1...i {
            if i % j == 0 {
                result[i-1] += 1
            }
        }
    }
    for (index, value) in result.enumerated() {
        if value > limit {
            result[index] = power
        }
    }
    return result.reduce(0,+)
}

 

구현에는 문제 없어보이지만

많은 문제에서 시간제한에 걸립니다.

 

중첩 for문 안에서

약수를 구하는 반복이

O(n) 걸리는 게 문제인 거 같습니다.

 

---

 

개선된 풀이

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var result = [Int]()
    for i in 1...number {
        result.append(0)
        for j in 1...Int(sqrt(Double(i))) {
            if i % j == 0 {
                if (j * j) == i {
                    result[i-1] += 1
                } else {
                    result[i-1] += 2
                }
            }
            if result[i-1] > limit {
                result[i-1] = power
                break
            }
        }
    }
    return result.reduce(0,+)
}

 

제곱근을 활용해서 약수를 구할 수 있다고 합니다.

 

다소 수학적이지는 않지만

제곱근과 약수의 상관관계를 알아봅시다.

 

100의 제곱근은 10입니다.

10의 약수 1,2,4,5,10이 나오고

100의 약수 1,2,4,5,10,20,25,50,100이 나옵니다.

 

보게 되면 100의 약수 개수가

제곱근(10)을 기준으로

10의 약수의 개수만큼 대칭을 이루고 있습니다.

 

1,2,4,5   10   20,25,50,100

 

즉 제곱근의 약수만 구해도

쉽게 약수의 개수를 유추하기 쉽습니다.

100번 반복할걸 10/1로 줄여줄 수 있습니다.

 

---

 

참고할만한 풀이

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var attack = [Int](repeating: 0, count: number+1)

    for i in 1...number {
        var c = i

        while c <= number {
            attack[c] += 1
            c += i
        }
    }
    attack = attack.map { $0 > limit ? power : $0 }
    return attack.reduce(0, +)
}

 

약수를 구하는 다른 방법이 있어 가져왔습니다.

 

이렇게 [Int](repeating: , count: )로 배열을 만들어 주는 게

나처럼 [Int]()에 append로 배열을 만드는 거보다

메모리면에서 훨씬 친환경적이라고 합니다.

 

---