Leetcode 2799

도토코·2025년 4월 24일

알고리즘 문제 풀이

목록 보기

41/44

문제

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.
Return the number of complete subarrays.

A subarray is a contiguous non-empty part of an array.

문제(번역)

주어진 배열 nums는 양의 정수로 구성되어 있습니다.

우리는 배열의 부분배열이 완전한(subarray) 경우를 다음 조건을 만족한다고 정의합니다:

부분배열에 포함된 서로 다른(distinct) 원소의 개수가 배열 전체에서 등장하는 서로 다른 원소의 개수와 같을 때, 이 부분배열은 완전한 부분배열이라고 합니다.

완전한 부분배열의 개수는 몇 개인지 구하세요.

예제

예시 1:

입력: nums = [1,3,1,2,2]
출력: 4
설명: 완전한 부분배열은 다음과 같습니다: [1,3,1,2], [1,3,1,2,2], [3,1,2], [3,1,2,2]

예시 2:

입력: nums = [5,5,5,5]
출력: 10
설명: 배열은 정수 5로만 이루어져 있기 때문에, 모든 부분배열이 완전한 부분배열입니다. 선택할 수 있는 부분배열의 개수는 10개입니다.

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        ans = 0 #완전한 부분배열의 개수 저장
        cnt = len(set(nums)) #부분배열에 등장하는 원소의 개수가 cnt와 같아야 완전한 부분배열
        n = len(nums) 

        for i in range(n): # 부분배열의 길이는 주어진 배열의 길이 이상이 될 수 없기에 주어진 배열의 길이만큼만 탐색 
            s = set()
            for j in range(i,n):
                s.add(nums[j])
                if len(s) == cnt:
                    ans += 1
        return ans

i의 변화:

i는 부분배열의 시작 인덱스를 나타낸다.
i는 0부터 n-1까지 증가하면서 배열의 각 원소를 시작점으로 하는 부분배열을 탐색한다.
즉, i는 배열의 모든 시작점을 순차적으로 탐색한다.

j의 변화:

j는 부분배열의 끝 인덱스를 나타낸다.
j는 i부터 시작해서 배열 끝까지 증가한다. 즉, j는 i를 기준으로 오른쪽으로 확장되면서, 각 부분배열을 점차적으로 확장한다.
j가 증가함에 따라, 부분배열에 새로운 원소가 추가되고, set에 그 원소가 추가된다. 이를 통해 현재 부분배열에 포함된 서로 다른 원소의 개수를 추적한다.

전체 흐름:
1. i가 0부터 n-1까지 반복되며, 각 i는 부분배열의 시작을 나타낸다.
2. 그에 따라 j는 i부터 n-1까지 반복되며, 각 j는 부분배열의 끝을 나타낸다.
3. s.add(nums[j])를 통해 set에 nums[j]를 추가하고, len(s)가 cnt와 같으면 완전한 부분배열을 찾았다는 의미로 ans를 증가시킨다.