[프로그래머스/c++/swift] 기사단원의 무기

 

https://school.programmers.co.kr/learn/courses/30/lessons/136798?language=swift 

프로그래머스

 

 

약수를 구할 때, 시간 초과 발생 -> 모든 수를 쭉 돌아서 생긴 문제

약수 구하기에 효율적으로 진행해야 됨

약수는 짝지어져 있으므로 i*i<=n 밑으로 for문을 돌리면 된다. 대신, 자기 자신을 두 번 곱하면 n이 나오므로 1번만 더한다.

 

c++

#include <string>
#include <vector>
using namespace std;

int calDivisor(int x){
    int cnt = 0;
    for(int i=1; i*i<=x; i++) {
        if(x % i == 0) {
            if(i*i == x) cnt += 1;
            else cnt += 2;
        }
    }
    return cnt;
}

int solution(int number, int limit, int power) {
    int answer = 1;
    for(int i=2; i<=number; i++){ //기사단원
        int divisor = calDivisor(i);
        answer += limit >= divisor ? divisor : power;
    }
    return answer;
}

 

swift

import Foundation

func calDivisor(x: Int) -> Int {
    var cnt = 0
    for i in 1...Int(sqrt(Double(x))) {
        if x % i == 0 {
            cnt += i * i == x ? 1 : 2
        }
    }
    return cnt
}

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var answer = 0
    for i in 1...number {
        let divisor = calDivisor(x: i)
        answer += limit >= divisor ? divisor : power
    }
    return answer
}