[리트코드] 3718 - Smallest Missing Multiple of K

3718. Smallest Missing Multiple of K

Easy

---

Given an integer array nums and an integer k, return the smallest positive multiple of k that is missing from nums.

A multiple of k is any positive integer divisible by k.

 

Example 1:

Example 2:

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

분류

배열, 해시 테이블

---

문제 풀이

문제 분석

이 문제는 정수 배열 nums와 정수 k가 주어졌을 때, nums에 존재하지 않는 k의 가장 작은 양의 배수를 찾는 문제입니다.

• 입력: 정수 배열 nums (길이 1100, 원소 값 1100), 정수 k (1~100)
• 출력: nums에 없는 k의 배수 중 최솟값 (정수)
• 핵심 조건: 배수는 양의 정수여야 하며 (k * 1, k * 2, ...), nums에 포함되지 않아야 합니다.

접근 방법

이 문제를 해결하기 위해 해시 집합(Hash Set) 자료구조를 사용합니다.

1. 자료구조 선택 이유: nums 배열에서 특정 값이 존재하는지 빠르게 확인해야 합니다. 리스트에서 in 연산을 사용하면 O(N) 시간이 걸리지만, 집합(Set)으로 변환하면 평균 O(1) 시간에 존재 여부를 확인할 수 있습니다.
2. 알고리즘: k의 배수를 1부터 순차적으로 증가시키며(k*1, k*2, k*3...), 해당 배수가 집합에 없는지 확인합니다. 없는 첫 번째 배수가 정답이 됩니다.
3. 종료 조건: 제약 조건상 nums의 원소 최댓값이 100이고 개수가 최대 100개이므로, k의 배수를 아무리 늦게 찾더라도 최대 101번째 배수(k * 101) 안에는 반드시 답이 존재합니다. 따라서 무한 루프를 돌려도 안전하게 종료됩니다.

구현 설명

1. 집합(Set) 생성

nums_set = set(nums)

• 입력 배열 nums를 집합 nums_set으로 변환합니다.
• 이를 통해 이후 배수 존재 여부 확인 시 O(1) 시간 복잡도를 보장받습니다.

2. 배수 탐색을 위한 인덱스 초기화

idx = 1

• k의 배수를 생성하기 위한 승수(곱해지는 수) idx를 1로 초기화합니다. 첫 번째 배수는 k * 1입니다.

3. 무한 루프를 통한 순차 탐색

while True:
    if k * idx in nums_set:
        idx += 1
        continue
    else:
        return k * idx

• while True 루프를 돌며 k * idx 값을 계산합니다.
• 존재하는 경우: 계산된 배수가 nums_set에 있다면 idx를 1 증가시켜 다음 배수를 확인합니다.
• 존재하지 않는 경우: 집합에 없다면 해당 값이 정답이므로 즉시 반환하고 함수를 종료합니다.

⏱복잡도 분석

• 시간 복잡도: O(N + M)

  • N은 nums 배열의 길이입니다. 집합 생성에 O(N)이 소요됩니다.
  • M은 정답이 되는 배수의 인덱스(idx) 값입니다. 최악의 경우 nums에 k의 배수가 1부터 연속해서 들어있어 M번 반복하게 됩니다. 제약 조건상 nums 원소 최댓값이 100이므로 M은 최대 101 정도이며, 상한이 정해져 있어 상수 시간에 가깝습니다. 따라서 전체적으로 O(N) 시간에 가깝게 동작합니다.

• 공간 복잡도: O(N)

  • nums의 모든 원소를 저장하기 위한 집합 nums_set을 사용하므로 입력 크기에 비례하는 공간이 필요합니다.

핵심 포인트

1. 빠른 조회를 위한 해시 집합(Hash Set) 활용: 리스트의 in 연산(O(N)) 대신 집합의 in 연산(O(1))을 사용하여 탐색 성능을 최적화했습니다.
2. 순차적 탐색의 정당성: k의 배수는 k, 2k, 3k... 순으로 커지므로, 1부터 순서대로 확인하여 처음 발견된 누락된 배수가 정답이 됩니다. 그리디(Greedy)한 접근이 최적해를 보장합니다.
3. 제약 조건을 활용한 종료 보장: 문제의 제약 조건(nums[i] <= 100, len(nums) <= 100) 덕분에 답이 항상 유한 범위 내에 존재하므로, 별도의 상한 제한 없이 while True 루프를 안전하게 사용할 수 있습니다.

풀이 코드

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        nums_set = set(nums)

        idx = 1
        while True:
            if k * idx in nums_set:
                idx += 1
                continue

            else:
                return k * idx