문제 소개
정수로 이루어진 배열 arr[]가 주어졌을 때, 각 하위 배열(subarray)에 포함된 서로 다른 요소(distinct elements)의 개수가 원본 배열의 서로 다른 요소 개수와 동일한 모든 하위 배열의 개수를 구하는 것이 목표입니다.
예를 들어, 원본 배열이 [1, 1, 2, 3]이라면 조건을 만족하는 하위 배열은 [1, 2, 3]과 [1, 1, 2, 3]입니다.
원본 배열의 서로 다른 요소는 총 3개이며, 두 하위 배열 역시 각각 서로 다른 요소를 3개씩 포함하고 있기 때문입니다.
예시로 이해하기
입력 − arr[] = {1, 2, 1, 2, 3, 4, 2}
출력 − 원본 배열과 동일한 서로 다른 요소 개수를 가진 하위 배열의 개수: 6
설명 − arr[]의 서로 다른 요소는 4개(1, 2, 3, 4)입니다. 동일한 개수의 서로 다른 요소를 가진 하위 배열은 다음과 같습니다(왼쪽에서 오른쪽으로 셈).
[1,2,1,2,3,4], [2,1,2,3,4], [1,2,3,4], [1,2,3,4,2], [2,1,2,3,4,2], [1,2,1,2,3,4,2]
입력 − arr[] = {8, 7, 5, 6, 10}
출력 − 원본 배열과 동일한 서로 다른 요소 개수를 가진 하위 배열의 개수: 1
설명 − arr[]의 서로 다른 요소는 5개(5, 6, 7, 8, 10)입니다. 동일한 개수를 만족하는 하위 배열은 [8, 7, 5, 6, 10] 단 하나뿐입니다.
프로그램에 적용된 접근 방식
정수 배열 arr[]를 입력받고 배열의 크기를 계산합니다.
sub_distinct(int arr[], int size) 함수는 배열을 인자로 받아 조건을 만족하는 하위 배열의 개수를 반환합니다.
결과를 저장할 임시 변수 count와 함께 right, left 변수를 선언합니다.
요소의 등장 정보를 저장하기 위해 unordered_map 타입의 변수 um을 선언합니다.
0부터 배열 크기까지 FOR 루프를 돌며 unordered_map에 arr[i] 값을 설정합니다.
unordered_map의 크기(고유 요소의 총 개수)를 계산한 뒤, map을 clear()로 비웁니다.
다시 0부터 배열 크기까지 FOR 루프를 시작합니다.
루프 내부에서 right < size이고 left < um_size인 동안 WHILE 루프를 실행합니다.
um[arr[right]] 값을 증가시키고, 그 값이 1이 되면(새로운 고유 요소가 등장하면) left를 1 증가시킵니다.
WHILE 루프가 끝나면 right를 1 증가시킵니다.
left == um_size라면 현재 위치 이후의 모든 확장이 조건을 만족하므로 count에 (size - right + 1)을 더합니다.
um[arr[i]] 값을 1 감소시키고, 그 값이 0이 되면(고유 요소가 사라지면) left를 1 감소시킵니다.
모든 반복이 끝나면 count를 반환하고 결과를 출력합니다.
이 알고리즘은 슬라이딩 윈도우(sliding window) 기법을 활용하여 각 시작 지점마다 윈도우를 오른쪽으로 확장해 가며 고유 요소의 개수를 추적합니다. 덕분에 이중 루프 전체 탐색보다 훨씬 효율적으로 답을 구할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int sub_distinct(int arr[], int size){
int count = 0, right = 0, left = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; ++i){
um[arr[i]] = 1;
}
int um_size = um.size();
um.clear();
for(int i = 0; i < size; ++i){
while (right < size && left < um_size){
++um[arr[right]];
if (um[arr[right]] == 1){
++left;
}
++right;
}
if (left == um_size){
count = count + (size - right + 1);
}
--um[arr[i]];
if (um[arr[i]] == 0){
--left;
}
}
return count;
}
int main(){
int arr[] = {4, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays having total distinct elements same as original array are: "<<sub_distinct(arr, size);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of subarrays having total distinct elements same as original array are: 1