1. 문제 소개

1390. Four Divisors

2. 나의 풀이

$\sqrt{n}$만큼만 약수를 확인하면 되며 약수의 개수가 4개를 넘어가면 중단하는 방식으로 속도를 높였다.

class Solution:                                          # LeetCode 제출 형식에 맞춘 Solution 클래스 정의
    def sumFourDivisors(self, nums: List[int]) -> int:   # 약수 개수가 4개인 수들의 약수 합을 구하는 함수
        ans = 0                                          # 전체 약수 합을 누적할 변수 초기화

        for n in nums:                                  # 입력 배열 nums의 각 정수 n을 순회
            temp = set()                                # 현재 숫자 n의 약수를 중복 없이 저장할 집합 생성
            for d in range(1, int(sqrt(n)) + 1):        # 1부터 sqrt(n)까지 약수 후보를 순회
                if len(temp) > 4:                       # 약수 개수가 이미 4개를 초과한 경우
                    break                               # 더 이상 탐색하지 않고 반복 종료

                if n % d == 0:                          # d가 n의 약수인 경우
                    temp.add(d)                         # d를 약수 집합에 추가
                    temp.add(n // d)                    # 대응되는 약수 n//d를 함께 추가

            if len(temp) == 4:                          # 약수의 개수가 정확히 4개인 경우에만
                for d in temp:                          # 해당 약수들을 하나씩 순회하며
                    ans += d                            # 전체 정답에 약수 값을 누적

        return ans                                      # 모든 수에 대해 계산한 최종 합을 반환

3. 다른 풀이

다른 풀이도 나와 비슷했으나 약수 개수가 4개인 수는 $p^3$ 또는 $p\times q$라는 사실을 이용할 수 도 있다고 한다.

4. 마무리

어제 오늘은 숫자와 관련된 문제가 많아서 좋았다.