[리트코드] 3550 - Smallest Index With Digit Sum Equal to Index

3550. Smallest Index With Digit Sum Equal to Index

Easy

---

You are given an integer array nums.

Return the smallest index i such that the sum of the digits of nums[i] is equal to i.

If no such index exists, return -1.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

분류

배열, 수학

---

문제 풀이

문제 분석

주어진 정수 배열 nums에서 **인덱스 i**와 해당 인덱스의 값 nums[i]의 각 자릿수 합이 같은 가장 작은 인덱스 i를 찾는 문제입니다.
만약 조건을 만족하는 인덱스가 없다면 -1을 반환합니다.

• 입력: 정수 배열 nums (길이 1 ~ 100, 원소 값 0 ~ 1000)
• 출력: 조건을 만족하는 가장 작은 인덱스 i (정수), 없으면 -1

---

접근 방법

이 문제는 완전 탐색(Brute Force) 방식으로 해결할 수 있습니다.
배열의 길이가 최대 100이고, 각 숫자도 최대 1000(최대 4자리)이므로 모든 인덱스를 순회하며 자릿수 합을 계산해도 연산량이 매우 적습니다(최대 100 * 4 = 400회 연산).

알고리즘 흐름:

1. 배열을 인덱스 i와 값 num을 함께 순회합니다(enumerate 사용).
2. 현재 값 num의 각 자릿수 합을 계산합니다.
3. 계산된 합이 현재 인덱스 i와 같으면 즉시 i를 반환합니다(가장 작은 인덱스부터 순회하므로 처음 발견된 것이 정답).
4. 순회가 끝날 때까지 조건을 만족하는 인덱스가 없으면 -1을 반환합니다.

---

구현 설명

1. 인덱스와 값 동시 순회

• enumerate(nums)를 사용하여 배열의 인덱스 i와 원소 num을 동시에 가져옵니다.
• 인덱스 0부터 순차적으로 확인하므로, 조건을 처음 만족하는 인덱스가 자동으로 가장 작은 인덱스가 됩니다.

2. 자릿수 합 계산

• 숫자 num을 문자열로 변환(str(num))한 뒤, 각 문자(자릿수)를 순회하며 정수로 변환해 누적합(total)을 구합니다.
• 예: num = 10 → "10" → '1', '0' → 1 + 0 = 1

3. 조건 비교 및 조기 반환

• 계산된 자릿수 합(total)과 현재 인덱스(i)를 비교합니다.
• 같다면 바로 return i를 수행하여 함수를 종료합니다. 더 이상 뒤의 인덱스를 볼 필요가 없습니다.

4. 예외 처리 (조건 불만족 시)

• for 루프가 끝까지 돌았는데 return되지 않았다면 조건을 만족하는 인덱스가 없는 것입니다.
• 루프 밖에서 return -1을 실행합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N * D)

  • N: 배열의 길이 (최대 100)
  • D: 숫자의 최대 자릿수 (최대 4, nums[i] <= 1000)
  • 각 원소마다 자릿수 합을 구하므로 N * D번 연산합니다. 제약 조건상 최대 400회로 매우 빠릅니다.

• 공간 복잡도: O(1)

  • 자릿수 합을 저장할 변수 total과 루프 변수 외에 추가적인 자료구조를 사용하지 않습니다.
  • 문자열 변환 시 잠시 메모리를 쓰지만 자릿수가 고정되어 상수 공간으로 간주합니다.

---

핵심 포인트

1. 작은 제약 조건 활용: 배열 길이(100)와 숫자 크기(1000)가 작아 완전 탐색으로 충분히 해결 가능합니다.
2. 자릿수 합 구하기: 숫자를 문자열로 변환해 한 글자씩 순회하는 것이 파이썬에서 가장 직관적이고 간편합니다. (수학적으로 num % 10, num // 10을 써도 됨)
3. 조기 종료(Early Return): 정답을 찾으면 즉시 반환하여 불필요한 연산을 줄이고, '가장 작은 인덱스' 조건을 자연스럽게 만족시킵니다.

풀이 코드

class Solution:
    def smallestIndex(self, nums: List[int]) -> int:
        for i,num in enumerate(nums):
            total = 0
            for x in str(num):
                total += int(x)

            if i == total:
                return i

        return -1