[리트코드] 3471 - Find the Largest Almost Missing Integer

3471. Find the Largest Almost Missing Integer

Easy

---

You are given an integer array nums and an integer k.

An integer x is almost missing from nums if x appears in exactly one subarray of size k within nums.

Return the largest almost missing integer from nums. If no such integer exists, return -1.

A subarray is a contiguous sequence of elements within an array.  

Example 1:

Example 2:

Example 3:

 

Constraints:

• 1 <= nums.length <= 50
• 0 <= nums[i] <= 50
• 1 <= k <= nums.length

분류

배열, 해시 테이블

---

문제 풀이

이 문제는 nums 배열과 정수 k가 주어졌을 때, '거의 누락된(almost missing)' 숫자 중 가장 큰 값을 찾는 문제입니다. '거의 누락된' 숫자는 nums 배열 내에서 크기 k인 부분 배열에 정확히 한 번만 나타나는 숫자를 의미합니다. 만약 그러한 숫자가 없으면 -1을 반환합니다.

문제 분석

주어진 정수 배열 nums와 정수 k를 사용하여, 다음 조건을 만족하는 숫자 x를 찾아야 합니다.

1. x는 nums 배열의 부분 배열 중 크기가 k인 부분 배열에 정확히 한 번만 나타나야 합니다.
2. 이러한 x 중에서 가장 큰 값을 반환해야 합니다.
3. 조건을 만족하는 x가 없으면 -1을 반환합니다.

입력 nums의 길이는 1부터 50까지, nums의 각 요소는 0부터 50까지, k는 1부터 nums.length까지입니다. 이 제약 조건은 문제 풀이에 중요한 힌트를 제공할 수 있습니다.

접근 방법

제공된 코드는 Counter를 사용하여 배열 내 각 숫자의 전체 빈도를 계산한 후, k 값에 따라 세 가지 주요 케이스로 나누어 처리하는 방식을 사용합니다. 이 접근 방식은 모든 가능한 크기 k 부분 배열을 탐색하는 대신, 문제의 정의와 배열의 특성을 이용한 매우 효율적인 방법을 채택합니다. 특히, '거의 누락된' 숫자의 정의와 숫자가 배열 내에서 유일하게 나타나는 경우(Counter 값이 1인 경우)의 관계에 대한 깊은 통찰을 활용합니다.

핵심 아이디어는 다음과 같습니다:

1. 전체 배열 내 빈도 계산: collections.Counter(nums)를 사용하여 각 숫자가 nums 전체에서 몇 번 등장하는지 파악합니다.
2. 특수 케이스 k=1: 크기가 1인 부분 배열은 [nums[i]] 형태입니다. 숫자가 정확히 하나의 부분 배열에 나타나려면, 배열 전체에서 딱 한 번만 나타나야 합니다.
3. 특수 케이스 k=len(nums): 크기가 len(nums)인 부분 배열은 nums 배열 자체 하나뿐입니다. 이 경우, nums 내의 모든 숫자는 '거의 누락된' 정의를 만족합니다.
4. 일반 케이스 1 < k < len(nums): 이 경우가 가장 중요하며, 코드는 nums[0]와 nums[-1]만 확인합니다. 이는 '거의 누락된' 숫자 (x)가 배열 nums 전체에서 한 번만 나타나는 경우 (cnt[x] == 1)에는, 해당 숫자가 배열의 첫 번째 요소(nums[0])이거나 마지막 요소(nums[-1])여야만 '정확히 하나의 부분 배열에 나타난다'는 조건을 만족한다는 수학적 속성(증명은 구현 설명 참조)에 기반합니다.

구현 설명

주어진 코드는 k의 값에 따라 경우를 나누어 처리합니다. collections.Counter를 사용하여 nums 배열의 각 요소 빈도를 미리 계산해 둡니다.

1. 숫자 빈도 계산 및 초기화

• cnt = Counter(nums): nums 배열 내 각 숫자의 등장 횟수를 Counter 객체 cnt에 저장합니다. 예를 들어, nums = [3,9,2,1,7]이면 cnt = {3:1, 9:1, 2:1, 1:1, 7:1}이 됩니다.
• answer = -1: '거의 누락된' 숫자를 저장할 변수를 answer라고 하고, 조건에 맞는 숫자가 없는 경우를 대비해 초기값을 -1로 설정합니다.

2. k = 1인 경우 처리

• if k == 1:: k가 1인 경우, 부분 배열의 크기는 1입니다. 즉, [nums[0]], [nums[1]], ..., [nums[n-1]]과 같은 부분 배열들이 존재합니다.
• for x, c in cnt.items():: cnt에 있는 모든 숫자 x와 그 빈도 c를 순회합니다.
• if c == 1:: 만약 어떤 숫자 x가 nums 배열 전체에서 정확히 한 번만 나타난다면 (즉, c가 1이면), 이 x는 크기가 1인 부분 배열 중 [x]에만 포함되므로 '거의 누락된' 숫자의 정의를 만족합니다.
• answer = max(answer, x): 이 조건을 만족하는 x 중 가장 큰 값을 answer에 저장합니다.

3. k = len(nums)인 경우 처리

• elif k == len(nums):: k가 nums 배열의 길이와 같은 경우, 크기 k인 부분 배열은 nums 배열 자체(nums[0...len(nums)-1]) 하나뿐입니다.
• 이 경우, nums 배열에 포함된 모든 숫자는 이 유일한 부분 배열에 나타나므로 '거의 누락된' 숫자의 정의를 만족합니다.
• answer = max(nums): 따라서 nums 배열의 모든 숫자 중 가장 큰 값을 answer로 설정합니다.

4. 1 < k < len(nums)인 일반적인 경우 처리

• else:: k가 1보다 크고 nums의 길이보다 작은 모든 다른 경우를 처리합니다.
• 이 부분이 이 풀이의 핵심입니다. '거의 누락된' 숫자 x가 배열 nums 전체에서 유일하게 나타나는 경우(cnt[x] == 1)라면, x가 '정확히 하나의 크기 k 부분 배열에 나타나는' 조건을 만족하려면 x는 반드시 nums의 첫 번째 요소(nums[0])이거나 마지막 요소(nums[-1])여야 한다는 수학적 속성이 있습니다.
  • 증명: nums 내에서 숫자 x가 인덱스 i에 위치한다고 가정합니다 (x = nums[i]). x를 포함하는 크기 k 부분 배열의 시작 인덱스 s는 max(0, i - k + 1) <= s <= min(i, len(nums) - k) 범위를 만족해야 합니다. x가 '정확히 하나의 크기 k 부분 배열에 나타난다'는 것은 이 범위 내에 s가 단 하나만 존재한다는 의미이며, 이는 max(0, i - k + 1) == min(i, len(nums) - k)를 만족할 때만 가능합니다. 이 조건을 분석하면 i가 0이거나 len(nums) - 1일 때만 성립함을 알 수 있습니다 (단, k=1이나 k=len(nums)인 특수 케이스 제외).
• if nums[0] in cnt: if cnt[nums[0]] == 1: answer = max(answer, nums[0]): nums의 첫 번째 요소 nums[0]가 nums 배열 전체에서 한 번만 나타난다면, nums[0]는 '거의 누락된' 숫자가 될 수 있으므로 answer를 업데이트합니다.
• if nums[-1] in cnt: if cnt[nums[-1]] == 1: answer = max(answer, nums[-1]): nums의 마지막 요소 nums[-1]가 nums 배열 전체에서 한 번만 나타난다면, nums[-1]는 '거의 누락된' 숫자가 될 수 있으므로 answer를 업데이트합니다.
• 이 두 경우를 통해 '거의 누락된' 숫자의 후보를 찾고 그 중 최댓값을 answer에 저장합니다.

5. 결과 반환

• return answer: 모든 경우를 처리한 후 최종적으로 answer 값을 반환합니다. 만약 아무 조건도 만족하는 숫자가 없었다면 초기값인 -1이 반환됩니다.

⏱복잡도 분석

• 시간 복잡도 (Time Complexity):

  • Counter(nums)를 만드는 데 O(N)의 시간이 소요됩니다. (여기서 N은 nums 배열의 길이입니다.)
  • k == 1 케이스에서 cnt.items()를 순회하는 데는 nums 내의 고유한 숫자의 개수(V)만큼 시간이 걸립니다. 최악의 경우 V는 N이므로 O(N)입니다.
  • k == len(nums) 케이스에서 max(nums)를 호출하는 데 O(N)의 시간이 소요됩니다.
  • else 케이스는 상수 시간 O(1)의 연산만 수행합니다.
  • 따라서 전체 시간 복잡도는 O(N)입니다.

• 공간 복잡도 (Space Complexity):

  • Counter(nums)는 nums 배열 내 고유한 숫자의 개수(V)에 비례하는 공간을 사용합니다. 최악의 경우 V는 N이므로 O(N)입니다.
  • 따라서 전체 공간 복잡도는 O(N)입니다.

핵심 포인트

1. '거의 누락된' 정의의 정확한 이해: "정확히 하나의 크기 k 부분 배열에 나타나는 숫자"라는 정의를 정확히 이해하는 것이 중요합니다. 이는 숫자가 배열 내에서 유일한 경우와 해당 숫자의 위치에 따라 다르게 해석됩니다.
2. 엣지 케이스(k=1, k=len(nums))의 효율적인 처리: k=1인 경우는 배열 전체에서 한 번만 등장하는 숫자를 찾는 문제로, k=len(nums)인 경우는 배열의 최댓값을 찾는 문제로 단순화됩니다. 이 두 엣지 케이스는 일반적인 경우보다 훨씬 간단하게 해결됩니다.
3. 1 < k < len(nums) 케이스의 수학적 통찰: '거의 누락된' 숫자가 배열 전체에서 한 번만 나타나는 숫자(cnt[x] == 1)인 경우, 해당 숫자가 nums[0] 또는 nums[len(nums)-1]일 때만 '정확히 하나의 크기 k 부분 배열에 나타난다'는 수학적 속성을 활용한 것이 이 풀이의 핵심입니다. 이 통찰이 없으면 일반적으로 훨씬 복잡한(예: O(N*K) 또는 O(N^2)) 슬라이딩 윈도우나 브루트 포스 방식을 시도하게 될 것입니다.

풀이 코드

from collections import Counter

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums)

        answer = -1
        if k == 1:
            for x,c in cnt.items():
                if c == 1:
                    answer = max(answer, x)

        elif k == len(nums):
            answer = max(nums)

        else:
            if nums[0] in cnt:
                if cnt[nums[0]] == 1:
                    answer = max(answer, nums[0])

            if nums[-1] in cnt:
                if cnt[nums[-1]] == 1:
                    answer = max(answer, nums[-1])

        return answer