[리트코드 2778] 특수 원소의 제곱합 — 1부터 끝까지 나누어지는 위치 검사

원제: Sum of Squares of Special Elements

문제 요약

길이 n인 1-indexed 정수 배열에서 위치 i가 n을 나누는 원소를 특수 원소라고 합니다. 특수 원소들의 제곱을 모두 더해 반환합니다.

조건과 입출력

1 <= nums.length == n <= 50, 1 <= nums[i] <= 50입니다. 문제의 위치 i는 1부터 시작하며, 특수 원소 조건은 n % i == 0입니다.

예제와 문제 자료

예제 1: nums = [1,2,3,4]이면 특수 위치는 1, 2, 4이고 제곱합은 1 * 1 + 2 * 2 + 4 * 4 = 21이므로 Output: 21입니다. 예제 2: nums = [2,7,1,19,18,3]이면 특수 위치는 1, 2, 3, 6이고 제곱합은 2 * 2 + 7 * 7 + 1 * 1 + 3 * 3 = 63이므로 Output: 63입니다.

풀이 아이디어

n을 나누는 위치만 합산하면 됩니다. 코드는 배열을 한 번 순회하며 각 위치가 조건을 만족하는지 검사합니다. 파이썬 인덱스는 0부터 시작하므로 코드의 i에 대응하는 문제의 1-indexed 위치는 i+1입니다. 따라서 n % (i+1) == 0이면 해당 위치가 n의 약수이고, 그 원소만 제곱해 더합니다. 각 위치를 빠짐없이 검사하므로 특수 원소를 모두 포함하고, 조건을 만족하지 않는 위치는 정의상 합에 넣지 않습니다.

코드의 핵심

n = len(nums)로 길이를 저장하고, 누적값 answer를 0으로 시작합니다. for i in range(n)은 파이썬 인덱스 0부터 n-1까지 방문합니다. 조건 n % (i+1) == 0은 1-indexed 위치가 n을 나누는지 검사하며, 참일 때 answer += nums[i] ** 2로 해당 원소의 제곱을 더합니다. 순회가 끝나면 answer를 반환합니다.

코드 추적: nums = [1,2,3,4]에서는 n = 4입니다. 인덱스 i = 0, 1, 3에서 각각 4 % 1, 4 % 2, 4 % 4가 0이므로 1², 2², 4²를 더해 answer = 21이 됩니다. i = 2는 4 % 3 != 0이므로 더하지 않습니다. nums = [2,7,1,19,18,3]에서는 n = 6이고 i = 0, 1, 2, 5가 조건을 만족합니다. 해당 값의 제곱을 더한 결과는 4 + 49 + 1 + 9 = 63입니다.

제출 코드

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        n = len(nums)
        answer = 0
        for i in range(n):
            if n % (i+1) == 0:
                answer += nums[i] ** 2

        return answer

복잡도

배열의 길이를 n이라 하면, 각 원소를 한 번씩 검사하므로 시간 복잡도는 O(n)입니다. n과 answer 외에 입력 크기에 비례하는 자료구조를 만들지 않으므로 보조 공간은 O(1)입니다. 반환하는 합계는 정수 하나입니다.

복습 포인트

문제의 위치는 1-indexed지만 코드의 배열 접근은 0-indexed이므로 조건에는 i가 아니라 i+1을 사용합니다. n은 배열 길이이므로 마지막 위치 n은 항상 특수 원소입니다.

출처

문제 원문