프로그래머스 Lv. 1 Swift 알고리즘 - 기사단원의 무기

알고리즘 풀면서 가장 어려운 문제가 효율성이다.

답을 찾아내는 알고리즘을 만들었지만 결국 오래 걸려서 시간 초과가 뜨면 어떤 부분을 효율화시켜야할지 고민이 깊어진다.

 

여러가지 방면으로 생각하다 약수의 개념에 대해서 조금 더 깊게 파보자는 생각이 들었다.

그렇게 찾게된 것이 약수의 대칭성..!

인수분해를 통해 약수를 하나하나 찾는 과정이 너무 비효율적으로 비용이 많이 들기에

값의 제곱근을 기준으로 under value의 약수가 존재한다면 대칭적인 약수 값이 존재한다는 뜻이다.

이러한 특성을 이용하여 3번째 만에 효율성 테스트를 통과했다.

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 간단하게 생각해서 number의 약수를 인수분해를 통해 직접 하나씩 다 찾아주고 그 값을 array에 저장한다.
2. 저장된 값들과 limit의 값들을 비교해보고 limit 보다 큰 값을 power 값으로 변경해준다.
3. 변경된 값들을 전부 더한다.
4. 하지만 (1)의 경우에 숫자가 커지면 커질수록 기하급수적인 cost가 발생한다.
5. 이를 막기 위해 모든 인수를 찾을 필요 없이 제곱근을 기준으로 under value 인수들만 찾아서 *2를 해준다.
6. 유의할 점은 4, 9, 16처럼 같은 값이 제곱근으로 중복되는 경우에 *2가 아닌 +1을 해주어야한다는 것이다.(대칭성이 없기 때문에)
7. 그 후 다 더해주면 끝.

 

 

* 첫번째 코드 (시간초과 오류)

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var countMeasure = 0
    var measureArray: [Int] = []
    var answer = 0

    for i in 1...number {
        for j in 1...i {
            if i % j == 0 {
                countMeasure += 1
            }
        }
        measureArray.append(countMeasure)
        countMeasure = 0
    }

    for i in 0..<measureArray.count {
        if measureArray[i] > limit {
            measureArray[i] = power
        }
    }

    return measureArray.reduce(0, +)
}

 

* 두번째 코드 (시간초과 오류)

import Foundation

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

    for i in 1...number {
        for j in 1...i {
            if i % j == 0 {
                countMeasure += 1
            }
        }
        if countMeasure > limit {
            countMeasure = power
        }
        answer += countMeasure
        countMeasure = 0
    }

    return answer
}

 

* 세번째 코드 (통과)

import Foundation

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

    for i in 1...number {
        if i == 1 {
            answer += 1
        } else {
            let sqrtValue = Int(floor(sqrt(Double(i))))

            for j in 1...sqrtValue {
                if j * j == i {
                    countMeasure += 1
                } else if i % j == 0 {
                    countMeasure += 2
                }
            }

            if countMeasure > limit {
                countMeasure = power
            }

            answer += countMeasure
            countMeasure = 0
        }
    }

    return answer
}

 

정리(Today I Learned)

1. Swift에서 제곱근을 구하는 메소드인 sqrt를 사용했다. 제곱근을 구하다보니 Double, Float 값만을 사용가능했는데 이를 내림하고 Int로 바꿔주는 과정이 굉장히 비효율적으로 보였다. 코드가 매우 더러워보이는데... 이런 사소한 부분을 더 깔끔하게 코드로 짜보고 싶다. sqrt 함수 자체를 건드려서 Double을 반환하는게 아닌 반올림, 올림, 내림 등이 반영된 Int로 반환하도록 해보는 것도 좋을듯.