프로그래머스 - Lv 1. 기사단원의 무기

문제
처음 문제를 풀었을 때, 실패를 하였는데 실패는 시간 초과였다. 이는 내가 시간 복잡도를 고려하지 못하였다. 우선 틀린 풀이부터 차례대로 비교해보자.

시간 초과한 풀이

func solutionFail(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var templarsPower: [Int] = [] // 기사들의 파워
    var weightOfIron: Int = 0
    
    for templar in 1...number {
        templarsPower.append(divisor(templar)) // 약수를 구한 후 약수들의 파워를 저장.
    }
    
    for (index, templarPower) in templarsPower.enumerated() {
        if templarPower > limit {
            // 기준보다 높을 경우 기준으로 맞추기
            templarsPower[index] = power
        } else {
            continue
        }
    }
    
    print(templarsPower)
    
    for weight in templarsPower {
        weightOfIron += weight
    }
    
    return weightOfIron
}

func divisor(_ number: Int) -> Int {
    return (1...number).filter { number % $0 == 0 }.count
}

1. 기사들의 파워는 number의 약수의 수로 이루어져있다.

   • 그리하여 func divisor(_ number: Int) -> Int 함수를 이용하여 숫자들의 약수의 수를 구한다. 이 때, 시간 복잡도는 입력된 숫자에 따라 시간이 증가하는 알고리즘이므로 O(n)이 된다.
   • for 문으로 divisor 함수를 실행하게 되므로 시간복잡도는 O(n^2)이 된다. 왜냐하면 for문안에 또 filter로 이중 반복문이 되버린다.

2. 기사들의 파워를 확인하고 limit와 비교하여 다시 power를 재설정한다.

   • 또 다시 for문으로 확인을 한 후 변경하기 때문에 O(n)이 된다.

3. 전체 무게를 계산한다.

   • 전체 마지막 Int를 출력하기 위해 배열에 있는 모든 값을 for문을 통해 더해서 값을 표시한다. 이때도 시간복잡도는 O(n)이 된다.

결과적으로 전체 시간 복잡도는 O(n^2)이 된다.

성공한 풀이

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var templarsPower: [Int] = [] // 기사들의 파워
    var weightOfIron: Int = 0
    
    for templar in 1...number {
        var templarPower = 0
        
        // 어차피 가운데 값을 기준으로 좌우 대칭이므로,
        // 단, 가운데 값을 제곱했을 때 입력된 값일 경우 이는 값을 +1 해줘야한다.
        for p in 1...Int(sqrt(Double(templar))) {
            if templar % p == 0 {
                if p * p == templar {
                    templarPower += 1
                } else {
                    templarPower += 2
                }
            }
        }
        
        templarPower = templarPower > limit ? power : templarPower
        
        templarsPower.append(templarPower)
    }
    
    print(templarsPower)
    
    weightOfIron = templarsPower.reduce(0) { $0 + $1 }
    
    return weightOfIron
}

1. 기사들의 파워는 number의 약수의 수로 이루어져있다.

   • 1...number 만큼 동작하는 for문 루프가 있다.
   • 내부에 또 for문이 존재하는데, 이는 약수를 구하는데 사용을 하게된다. 하지만 여기에서는 templar의 제곱근까지만 확인하므로 시간복잡도는 O(n의 제곱근)이 된다.

2. 기사들의 파워를 확인하고 limit와 비교하여 다시 power를 재설정한다.

   • 이 때 삼항연산자를 사용하게 되는데 이는 시간 복잡도에 큰 영향을 미치지 않고, 조건문의 결과에 따라 두가지 중 하나의 값을 서너택하므로 실행 시간은 입력 크기에 따라 일정하게 유지되어 O(1)이 된다.

3. 전체 무게를 계산한다.

   • reduce()를 이용하여 배열의 합을 구하는데 이 때 O(n)의 시간이 걸린다.

결과적으로 전체 시간 복잡도는 O(n + n의 제곱근)이 된다.

결론

비교하였을 때, 시간복잡도가 더 낮은 것을 선택하여 입력이 커질수록 성능이 더 우수한 것으로 제출해야한다!