문제 소개
정수 요소로 이루어진 배열 arr[]가 주어집니다. 우리의 목표는 각 부분 배열이 중복되지 않는 고유한 요소만을 포함하도록 할 때, 이러한 부분 배열의 요소들로 만들 수 있는 쌍(pair)의 총 개수를 구하는 것입니다.
예를 들어 배열이 [1, 2, 2, 3, 3]이라면, 고유한 요소만 포함하는 부분 배열은 [1, 2]와 [2, 3]입니다. 여기서 만들 수 있는 쌍은 (1, 2)와 (2, 3)이므로, 쌍의 개수는 2가 됩니다.
예제로 이해하기
예제 1
입력: arr[] = {1, 2, 5, 3}
출력: 고유한 요소를 가진 부분 배열로 형성된 쌍의 개수: 6
설명: 고유한 요소만 포함하는 부분 배열은 [1, 2, 5, 3]이며, 가능한 쌍은 (1, 2), (1, 3), (1, 5), (2, 5), (2, 3), (5, 3)으로 총 6개입니다.
예제 2
입력: arr[] = {1, 2, 1, 2, 3}
출력: 고유한 요소를 가진 부분 배열로 형성된 쌍의 개수: 5
설명: 고유한 요소만 포함하는 부분 배열과 각각의 쌍은 다음과 같습니다.
[1, 2] → 쌍: (1, 2)
[2, 1] → 쌍: (2, 1)
[1, 2, 3] → 쌍: (1, 2), (2, 3), (1, 3)
총 쌍의 개수: 5
알고리즘 접근 방식
이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 활용해 효율적으로 해결할 수 있습니다. 프로그램의 동작 과정은 다음과 같습니다.
- 정수 배열을 입력으로 받습니다.
- distinct_pairs(int arr[], int size) 함수는 배열과 그 크기를 인자로 받아, 고유한 요소를 가진 부분 배열로 형성된 쌍의 개수를 반환합니다.
- 초기 카운트(count)는 0으로, 변수 start와 end는 모두 0으로 설정합니다.
- 현재 윈도우에 포함된 요소를 표시하기 위해 크기가 size이고 false로 초기화된 벡터 check를 선언합니다.
- start가 size보다 작은 동안 WHILE 루프를 반복합니다.
- 첫 번째 내부 루프에서는 start가 size보다 작고 check[arr[start]]가 false인 동안, count에 (start - end)를 더하고, check[arr[start]]를 true로 설정한 뒤 start를 1 증가시킵니다.
- 두 번째 내부 루프에서는 end가 start보다 작고, start가 size와 같지 않으며 check[arr[start]]가 true인 동안, check[arr[end]]를 false로 설정하고 end를 1 증가시켜 윈도우의 왼쪽 경계를 이동시킵니다.
- 모든 탐색이 끝나면 최종 count를 반환합니다.
- 결과를 출력합니다.
참고로 이 구현에서 check 벡터는 배열의 값 자체를 인덱스로 사용하므로, 배열의 요소는 음수가 아니며 배열 크기보다 작은 값을 가진다는 전제 조건이 필요합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
int count = 0;
int start = 0;
int end = 0;
vector<bool> check(size, false);
while (start < size){
while (start < size && !check[arr[start]]){
count += (start - end);
check[arr[start]] = true;
start++;
}
while (end < start && (start != size && check[arr[start]])){
check[arr[end]] = false;
end++;
}
}
return count;
}
int main(){
int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of pairs formed by distinct element sub-arrays are: 17
마무리
이 알고리즘은 각 요소가 윈도우에 최대 한 번 추가되고 한 번 제거되므로 시간 복잡도는 O(n)입니다. 모든 부분 배열을 일일이 확인하는 완전 탐색 방식(O(n²) 이상)과 비교하면, 슬라이딩 윈도우 기법을 활용하면 훨씬 효율적으로 쌍의 개수를 계산할 수 있다는 점이 핵심입니다.