[C++, python] 프로그래머스 - 기사단원의 무기

문제 링크

프로그래머스

문제 풀이

이 문제는 1부터 number까지의 자연수들의 약수의 갯수를 구해야하는 문제이다.

자연수 n의 약수를 구하는 법은 쉽다. 반복문을 1부터 n까지 돌려 n을 i로 나누었을 때 나머지가 없을 경우, i를 약수라고 하기 때문에 반복문을 잘 써주면 된다.

하지만 이 문제에서는 시간복잡도가 중요하기 때문에 우리는 보다 적은 반복만으로 약수를 구해야만 한다.

대부분의 약수는 짝이 존재하기 때문에, 반복문을 반만 돌려도 약수를 찾는데에는 무리가 없을 것이다.
여기서, 더 나아가자면, 자연수 n의 약수의 반은 n의 제곱근 사이에 존재한다. 그 이유는 n제곱근이 자연수라면, 그 또한 약수가 될 것이고 n제곱근이 약수의 절반 지점이기 때문이다.

따라서 약수 탐색의 범위를 n 제곱근까지로 정한 뒤 약수를 찾으면 제한 시간 내에 모든 약수를 찾을 수 있다.

정답 코드

C++

#include <string>
#include <vector>
#include <cmath>
#include <numeric>

using namespace std;

int get_power(int num) {
    int cnt = 0;
    for (int i = 1; i < (int)(pow(num, 0.5)) + 1; i++) {
        if (num % i == 0) {
            cnt++;
            if ((int)pow(i, 2) != num)
                cnt++;
        }
    }
    return cnt;
}

int solution(int number, int limit, int power) {
    int answer = 0;
    for (int i = 1; i <= number; i++) {
        int p = get_power(i);
        (p > limit) ? answer += power : answer += p;
    }
    return answer;
}

python

def get_power(num):
    cnt = 0
    for i in range(1, int(num ** (0.5)) + 1):
        if num % i == 0:
            cnt += 1
            if (i ** 2 != num) :
                cnt += 1
    return cnt

def solution(number, limit, power):
    answer = 0
    for i in range(1, number + 1):
        k = get_power(i)
        answer += k if k <= limit else power
    return answer

단순한 if ~ else 구조라면, 삼항연산자의 사용을 추천한다.

C++ 삼항연산 : (조건) ? (조건이 맞다면 해야하는 동작) : (조건이 틀리다면 해야하는 동작); 의 꼴로, 한줄짜리의 조건문들을 줄이는데 너무 좋다.

개인적으로 파이썬이 문제푸는데 정말 편한 언어라고 생각하지만, 삼항연산자 형태는 아직도 익숙치가 않다.

python 삼항연산 : (조건이 맞다면 해야하는 동작) if (조건) else (조건이 틀리다면 해야하는 동작)