Programming/Algorithm & Data Structure
[Swift] 프로그래머스 코딩테스트 연습> 연습문제> 기사단원의 무기
guswlsdk
2023. 1. 5. 18:27
반응형
풀이
기사단원의 번호를 순회하기 위한 포문과 약수를 구하기 위한 포문 두 개의 이중 포문으로 구현하면 number가 최댓값인 100,000일 때 시간복잡도는 백만의 제곱이 되므로 시간초과이다.
메모라이징을 써야할지 고민했는데(아직 감이 없음...) 수학을 응용한 방법이 있었다.
number가 10일 때의 약수는 1, 2, 5 10
number가 16일 때의 약수는 1, 2, 4, 8, 16
number가 20일 때의 약수는 1, 2, 5, 10, 20 ......
무언가 1부터 number까지 포문이 순회하지 않아도 될 것 같다.
16일 때의 약수는 1, 2, 4, 8, 16이면 1, 2는 무언가 곱해져서 약수가 된다. 쌍이 있다는 말이다.
4는 같은 숫자 4가 곱해져 약수가 된 것이다.
절반쯤만 구하면 되는데 그 절반이 어디일까????
1부터 16의 제곱근인 4까지만 순회하면 된다.
순회하는 변수 i가 16의 약수일 때 약수의 갯수를 더하자.
약수는 쌍이 있으므로 나누어 떨어질 때마다 count + 2를 해주면 되고,
i * i 가 16일 때는 쌍이 없으므로 count + 1 해주자
코드
func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
func getMeasure(n: Int) -> Int{
var count = 0
for i in 1...Int(sqrt(Double(n))){
if n%i == 0{
if i*i == n{
count += 1
}else{
count += 2
}
}
}
return count
}
var result = 0
for num in 1...number{
let measure = getMeasure(n: num)
if measure > limit{
result += power
}else{
result += measure
}
}
return result
}
반응형