정수 요소로 구성된 배열이 주어졌을 때, (arr[i], arr[j]) 형태의 쌍 중에서 인덱스 조건 i < j를 만족하면서 값의 중복이 없는 고유한 쌍의 개수를 구하는 것이 목표입니다.
예제로 이해하기
입력 − arr[] = {1, 2, 3};
출력 − i < j인 고유 쌍 (arr[i], arr[j])의 개수 − 3
설명 − 모든 요소가 고유하므로 가능한 쌍은 다음과 같습니다.
(1,2) - ( arr[0], arr[1] ) 0<1 (1,3) - ( arr[0], arr[2] ) 0<2 (2,3) - ( arr[1], arr[2] ) 1<2
입력 − arr[] = {4, 4, 3, 2};
출력 − i < j인 고유 쌍 (arr[i], arr[j])의 개수 − 4
설명 − 동일한 값을 가진 쌍은 한 번만 계산되므로 고유한 쌍은 다음과 같습니다.
(4,4) - ( arr[0], arr[1] ) 0<1 (4,3) - ( arr[0], arr[2] ) 0<2 (4,2) - ( arr[0], arr[3] ) 0<3 (3,2) - ( arr[2], arr[3] ) 2<3
방법 1: 단순(Naive) 접근
두 개의 for 루프를 사용하여 배열 arr[]을 순회합니다. 바깥 루프는 i=0부터 i<size-1까지, 안쪽 루프는 j=i+1부터 j<size까지 진행하므로 항상 i<j 조건이 유지됩니다. 이때 각 쌍 (arr[i], arr[j])을 set<pair<int, int>> 타입의 집합 'se'에 삽입합니다. set은 중복을 허용하지 않으므로, 모든 순회가 끝난 후 'se'의 크기(size)가 곧 고유 쌍의 개수가 됩니다.
- 정수 요소를 가진 배열 arr[]와 그 크기 size를 받습니다.
- 함수 unique_pair(int arr[], int size)는 배열과 길이를 매개변수로 받아, 쌍 (arr[i], arr[j])에서 인덱스 i<j를 만족하는 고유 쌍의 개수를 반환합니다.
- count의 초기값을 0으로 설정합니다.
- 정수 쌍을 저장할 집합 'se'(set<pair<int, int>>)를 선언합니다.
- 두 개의 for 루프로 arr[]을 순회합니다. i=0부터 i<size-1까지, j=i+1부터 j<size까지입니다.
- 각 쌍은 항상 i<j를 만족하므로 se.insert(make_pair(arr[i], arr[j]))를 통해 'se'에 삽입합니다.
- 모든 루프가 종료되면 count = se.size()로 갱신합니다.
- count에는 'se'에 저장된 고유 쌍의 개수가 들어 있습니다.
- count를 결과로 반환합니다.
방법 2: 효율적인(Efficient) 접근
이 방식에서는 각 요소 뒤에 위치한 고유한 요소들의 개수를 활용합니다. arr[i]는 arr[i+1]부터 arr[size-1]까지 범위의 서로 다른 요소들과만 쌍을 이루며, arr[i] 뒤에 고유한 요소가 x개 있다면 arr[i]는 x개의 쌍을 만들 수 있습니다. 따라서 먼저 각 인덱스 i 뒤에 있는 고유 요소의 개수를 기록하는 보조 배열을 만든 뒤, 이 값들을 모두 더해 전체 고유 쌍의 개수를 구합니다.
- 정수 요소를 가진 배열 arr[]와 그 크기 size를 받습니다.
- count의 초기값을 0으로, 임시 변수 temp도 0으로 설정합니다.
- 길이가 size인 배열 arr_2[]를 선언하고 arr_2[size-1] = 0으로 초기화합니다. 마지막 요소 뒤에는 어떤 요소도 없기 때문입니다.
- 정수형 집합 check와 uncheck 두 개를 생성합니다.
- 배열을 마지막 요소부터 첫 번째 요소까지 역순으로 순회합니다(i=size-1부터 i>=0까지). 집합 check에서 arr[i]를 찾습니다.
- 찾지 못했다면 아직 등장하지 않은 고유한 값이므로 temp를 증가시키고 arr_2[i] = temp로 설정합니다.
- 이미 존재한다면 temp를 증가시키지 않고 arr_2[i] = temp만 설정합니다.
- arr[i]를 check에 삽입합니다. 이후 같은 값이 다시 등장해도 고유 요소로 간주되지 않습니다.
- 역순 순회가 끝나면 arr_2[]에는 각 인덱스 뒤의 고유 요소 개수가 저장됩니다.
- 이제 arr[]을 i=0부터 i<size-1까지 순회하면서 각 arr[i]가 집합 uncheck에 있는지 확인합니다. 없다면 처음 등장한 값이므로 arr_2[i](arr[i] 뒤의 고유 요소 개수)를 count에 더하고, 이미 있다면 건너뜁니다.
- arr[i]를 uncheck에 삽입하여 이후 동일한 값이 중복 계산되지 않도록 합니다.
- 최종적으로 count에는 i<j 조건을 만족하는 고유 쌍 (arr[i], arr[j])의 개수가 저장됩니다.
- count를 결과로 반환합니다.
예제 코드 (단순 접근)
#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
int count = 0;
set<pair<int, int>> se;
for(int i = 0; i < (size - 1); i++){
for (int j = i + 1; j < size; j++){
se.insert(make_pair(arr[i], arr[j]));
}
}
count = se.size();
return count;
}
int main(){
int arr[] = { 4, 3, 1, 6, 7 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"i < j인 고유 쌍 (arr[i], arr[j])의 개수: "<<unique_pair(arr, size);
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
i < j인 고유 쌍 (arr[i], arr[j])의 개수: 10
예제 코드 (효율적인 접근)
#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
int count = 0, temp = 0;
int arr_2[size];
arr_2[size-1] = 0;
set<int> check, uncheck;
for (int i = size - 1; i > 0; i--){
auto set = check.find(arr[i]);
if (set != check.end()){
arr_2[i - 1] = temp;
}
else{
arr_2[i - 1] = ++temp;
}
check.insert(arr[i]);
}
for (int i = 0; i < size - 1; i++){
auto set = uncheck.find(arr[i]);
if (set != uncheck.end()){
continue;
}
count += arr_2[i];
uncheck.insert(arr[i]);
}
return count;
}
int main(){
int arr[] = { 4, 3, 1, 6, 7 };
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"i < j인 고유 쌍 (arr[i], arr[j])의 개수: "<<unique_pair(arr, size);
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
i < j인 고유 쌍 (arr[i], arr[j])의 개수: 10