N개의 요소로 구성된 배열이 주어졌을 때, 목표는 값이 서로 같으면서 인덱스가 다른 쌍 (i, j), 즉 Arr[i] == Arr[j]이고 i != j인 인덱스 쌍의 개수를 찾는 것입니다. 이는 같은 크기의 장갑을 한 짝씩 묶는 상황으로 비유할 수 있습니다. N개의 장갑 중에서 실제로 판매할 수 있는 것은 크기가 맞는 한 쌍뿐입니다.
이 문제는 두 개의 반복문을 사용하여 해결할 수 있습니다. 바깥쪽 반복문은 0 <= i < n-1 범위에서, 안쪽 반복문은 i < j < n 범위에서 실행합니다. 각 쌍 (i, j)에 대해 Arr[i] == Arr[j] && Arr[i] > 0 && Arr[j] > 0 조건을 검사하고, 참이라면 쌍의 개수를 1 증가시킨 뒤 해당 요소들을 -1로 변경(Arr[i] = Arr[j] = -1)하여 이후 검사에서 제외합니다. 장갑의 크기는 -1일 수 없기 때문입니다.
예제로 이해하기
입력 − Arr[]= { 4,3,2,1,2,4 }, N=6
출력 − 동일한 요소를 가진 인덱스 쌍의 개수 − 2
설명 −
count=0, Arr[]= [ 4,3,2,1,2,4 ]
Arr[0]=Arr[5], 0!=5, count=1, Arr[0]=Arr[5]=-1 → [ -1,3,2,1,2,-1 ]
Arr[2]=Arr[4], 2!=4, count=2, Arr[2]=Arr[4]=-1 → [ -1,3,-1,1,-1,-1 ]
더 이상 값이 같고 i != j이며 -1보다 큰 새로운 쌍이 없습니다. 전체 쌍 = 2
입력 − Arr[]= { 2,2,2,2,2 }, N=5
출력 − 동일한 요소를 가진 인덱스 쌍의 개수 − 2
설명 −
count=0, Arr[]= [ 2,2,2,2,2 ]
Arr[0]=Arr[1], 0!=1, count=1, Arr[0]=Arr[1]=-1 → [ -1,-1,2,2,2 ]
Arr[2]=Arr[3], 2!=3, count=2, Arr[2]=Arr[3]=-1 → [ -1,-1,-1,-1,2 ]
더 이상 새로운 쌍이 없습니다. 전체 쌍 = 2
프로그램에서 사용된 접근 방식
장갑 크기를 나타내는 0보다 큰 임의의 정수로 초기화된 정수 배열 Arr[]를 준비합니다.
배열의 길이를 저장하는 변수 n을 선언합니다.
함수 countPairs(int arr[], int n)는 배열과 그 길이를 입력받아 크기가 같고 인덱스가 서로 다른 쌍의 개수를 반환합니다.
두 개의 for 반복문을 사용하여 각 쌍을 이루는 요소들을 순회합니다.
바깥쪽 반복문은 0 <= i < n-1, 안쪽 반복문은 i < j < n 범위로 실행합니다.
arr[i]와 arr[j]가 양수인지 먼저 확인합니다. 그리고 arr[i] == arr[j]라면 count를 증가시킵니다. (반복문 조건상 i는 절대 j와 같을 수 없으므로 별도의 비교가 필요하지 않습니다.)
arr[i] = arr[j] = -1로 설정하여 이미 짝지어진 요소들이 이후 비교에서 제외되도록 합니다.
모든 반복문이 종료되면 count에는 장갑 한 쌍의 총 개수가 저장됩니다.
count를 결과로 반환합니다.
이 알고리즘의 시간 복잡도는 O(n²)이며, 추가적인 공간 없이 배열 자체만으로 처리하므로 공간 복잡도는 O(1)입니다.
예제 코드
// 위 접근 방식의 C++ 구현
#include <bits/stdc++.h>
using namespace std;
// 동일한 요소를 세어 장갑 한 쌍을 만드는 함수
int countPairs(int arr[], int n){
int count = 0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(arr[i]==arr[j] && arr[i]>0 && arr[j]>0){
count++;
arr[i]=arr[j]=-1;
}
}
}
return count;
}
int main(){
int arr[] = { 1,2,4,2,1,2,4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Pair of gloves ( Equal element pairs ):"<<countPairs(arr, n);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Pair of gloves ( Equal element pairs ):3.