[리트코드] 3731 - Find Missing Elements

3731. Find Missing Elements

Easy

---

You are given an integer array nums consisting of unique integers.

Originally, nums contained every integer within a certain range. However, some integers might have gone missing from the array.

The smallest and largest integers of the original range are still present in nums.

Return a sorted list of all the missing integers in this range. If no integers are missing, return an empty list.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

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

분류

배열, 해시 테이블, 정렬

---

문제 풀이

문제 분석

주어진 정수 배열 nums는 원래 특정 범위 내의 모든 정수를 포함하고 있었으나, 일부 정수가 누락된 상태입니다. 배열에는 중복된 값이 없으며(unique), 원래 범위의 최솟값과 최댓값은 여전히 배열에 존재한다고 보장됩니다.
우리의 목표는 이 최솟값부터 최댓값까지의 연속된 범위에서 nums에 존재하지 않는 정수들을 찾아 오름차순으로 반환하는 것입니다. 누락된 정수가 없다면 빈 리스트를 반환합니다.

• 입력: 고유한 정수로 이루어진 배열 nums (길이 2100, 값 1100)
• 출력: 누락된 정수들을 오름차순으로 담은 리스트

---

접근 방법

이 문제는 **해시 셋(Hash Set)**을 이용하여 효율적으로 해결할 수 있습니다.

1. 범위 파악: 배열을 한 번 순회하며 최솟값(min_num)과 최댓값(max_num)을 찾습니다. 이것이 원래 범위의 경계가 됩니다.
2. 존재 여부 빠른 확인: 배열의 모든 요소를 해시 셋(visited)에 저장합니다. 해시 셋은 특정 값이 존재하는지 확인하는 연산(lookup)의 시간 복잡도가 평균 **O(1)**이므로, 이후 범위 내의 모든 숫자를 검사할 때 매우 빠릅니다.
3. 누락된 숫자 탐색: min_num부터 max_num - 1까지의 모든 정수 i에 대해, i가 셋에 없다면 결과 리스트에 추가합니다. 최댓값은 문제 조건상 반드시 존재하므로 검사에서 제외해도 되지만, 코드에서는 range(min_num, max_num)을 사용하여 최댓값 직전까지 자연스럽게 처리합니다.

자료구조로 Set을 선택한 이유는 중복 제거가 자동으로 되고, 조회 속도가 O(1)로 배열이나 리스트의 O(N)보다 압도적으로 빠르기 때문입니다. 제약 조건(nums.length ≤ 100)이 작아 정렬 후 인접 원소 비교 등도 가능하지만, Set 기반 풀이가 가장 직관적이고 일반적입니다.

---

구현 설명

1. 초기화 및 배열 순회 (최솟값, 최댓값, 방문 집합 생성)

• 코드는 visited라는 빈 셋(Set)을 만들고, min_num은 무한대, max_num은 0으로 초기화합니다.
• nums 배열의 각 원소 num을 순회하며:
  • visited.add(num): 현재 숫자를 집합에 추가하여 '존재함'을 표시합니다.
  • min_num = min(min_num, num): 지금까지 본 숫자 중 최솟값을 갱신합니다.
  • max_num = max(max_num, num): 지금까지 본 숫자 중 최댓값을 갱신합니다.
• 이 단계를 통해 **원래 범위의 경계(min_num, max_num)**와 **존재하는 숫자들의 집합(visited)**을 동시에 확보합니다.

2. 누락된 숫자 탐색 및 결과 리스트 구성

• 빈 리스트 answer를 생성합니다.
• range(min_num, max_num)을 사용하여 min_num부터 max_num - 1까지의 모든 정수 i를 순회합니다. (최댓값 max_num은 문제 조건상 무조건 존재하므로 확인할 필요 없습니다.)
• 각 i에 대해 if not i in visited: 조건으로 셋에 없는지 확인합니다.
• 만약 없다면 answer.append(i)를 통해 결과 리스트에 추가합니다. range가 오름차순으로 생성되므로 결과 리스트도 자연스럽게 정렬됩니다.

3. 결과 반환

• 완성된 answer 리스트를 반환합니다. 누락된 숫자가 없다면 빈 리스트가 그대로 반환됩니다.

---

⏱복잡도 분석

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

  • N은 nums 배열의 길이입니다. 첫 번째 루프에서 배열을 한 번 순회하므로 O(N)입니다.
  • M은 원래 범위의 크기(max_num - min_num)입니다. 두 번째 루프에서 범위 내 모든 정수를 검사하므로 O(M)입니다.
  • 셋(Set)의 삽입과 조회는 평균 O(1)이므로 루프 내부 연산은 상수 시간입니다.
  • 제약 조건상 N ≤ 100, 값의 범위 ≤ 100이므로 M도 최대 100이며, 전체 연산은 매우 빠릅니다.

• 공간 복잡도: O(N + M) (또는 O(N))

  • visited 셋에 nums의 모든 원소를 저장하므로 O(N)의 공간이 필요합니다.
  • answer 리스트에는 최악의 경우(배열에 최솟값과 최댓값만 있는 경우) 범위 내 거의 모든 숫자가 담길 수 있으므로 O(M)의 공간이 필요합니다.
  • 일반적으로 입력 크기에 비례하는 O(N)으로 보거나, 출력 크기를 포함해 O(N + M)으로 표기합니다.

---

핵심 포인트

1. 범위 결정: 문제에서 "최솟값과 최댓값은 여전히 존재한다"는 조건을 이용해 별도의 입력 없이 배열 순회만으로 전체 범위(min_num ~ max_num)를 알 수 있습니다.
2. 해시 셋(Hash Set) 활용: 특정 숫자의 존재 여부를 O(1) 시간에 확인하기 위해 Set 자료구조를 사용했습니다. 리스트로 in 연산을 쓰면 O(N)이 걸려 비효율적입니다.
3. 자연스러운 정렬: range(min_num, max_num)을 사용해 최솟값부터 최댓값 이전까지 순차적으로 검사하면, 누락된 숫자를 발견하는 순서 자체가 오름차순이 되어 별도의 정렬 과정 없이 정렬된 결과를 얻을 수 있습니다.

풀이 코드

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        visited =set()
        min_num = float("inf")
        max_num = 0
        for num in nums:
            visited.add(num)
            min_num = min(min_num,num)
            max_num = max(max_num,num)

        answer = []
        for i in range(min_num,max_num):
            if not i in visited:
                answer.append(i)

        return answer