정수 값으로 이루어진 임의 크기의 배열 arr[]가 주어졌을 때, 두 요소의 합 역시 같은 배열 안에 존재하는 고유한 쌍(distinct pairs)의 개수를 계산하는 것이 목표입니다.
배열은 동일한 타입의 요소들을 정해진 크기만큼 순차적으로 저장할 수 있는 기본적인 자료구조입니다. 데이터 집합을 저장하는 용도로 사용되며, 같은 타입 변수들의 모음으로 이해하면 더욱 직관적으로 활용할 수 있습니다.
기억해야 할 핵심 사항
쌍은 요소의 순서에 관계없이 한 번만 계산됩니다. 예를 들어 (3, 2)와 (2, 3)은 서로 다른 쌍이 아니라 하나의 쌍으로 간주되어 1회만 카운트됩니다.
배열에 동일한 숫자가 여러 번 등장하더라도, 하나의 쌍을 만들 때는 정확히 두 번만 고려됩니다. 예를 들어 배열이 {2, 2, 2, 2}라면 만들어지는 쌍은 (2, 2) 하나뿐이므로 카운트는 1입니다.
예시
입력 − int arr = {6, 4, 10, 14}
출력 − 개수는 2설명 − 두 요소의 합이 배열에 존재하는 쌍은 (6, 4)와 (10, 4)이므로 개수는 2입니다.
입력 − int arr = {6, 6, 6, 6, 6, 13}
출력 − 개수는 0설명 − 합이 같은 배열 안에 존재하는 쌍이 하나도 없으므로 개수는 0입니다.
알고리즘 접근 방식
배열(예: arr[])을 생성하고 초기화합니다.
sizeof 연산자나 length() 함수를 이용해 배열의 길이를 계산합니다. 이 값은 배열의 요소 수에 해당하는 정수입니다.
결과를 저장할 카운트 변수를 선언합니다.
각 요소의 등장 횟수를 저장할 map<int, int> 타입 변수(예: mymap)를 생성합니다.
반복문을 돌면서 모든 요소의 빈도를 mymap에 기록합니다. 이렇게 하면 특정 합이 배열에 존재하는지 O(log n) 시간에 확인할 수 있습니다.
중복 쌍 제거를 위해 pair<int, int>를 키로 사용하는 또 다른 맵 변수(예: p)를 생성합니다.
i를 0부터 배열 크기 미만까지 반복하는 바깥쪽 루프를 시작합니다.
바깥쪽 루프 안에서 j를 i+1부터 배열 크기 미만까지 반복하는 안쪽 루프를 시작합니다.
안쪽 루프에서 mymap[arr[i] + arr[j]] > 0이고 p[{arr[i], arr[j]}] == 0이라면, 즉 현재 쌍의 합이 배열에 존재하면서 아직 세지 않은 새로운 쌍이라면 카운트를 1 증가시킵니다.
p[{arr[i], arr[j]}]와 p[{arr[j], arr[i]}]를 각각 1 증가시켜 순서만 다른 동일한 쌍이 중복으로 카운트되지 않도록 합니다.
모든 반복이 끝나면 카운트를 반환하고 결과를 출력합니다.
이 방법은 이중 반복문으로 모든 쌍을 검사하므로 시간 복잡도는 O(n² log n)이며, 추가 공간 복잡도는 O(n)입니다.
예제 코드
#include <iostream>
#include <map>
using namespace std;
// ar[0..n-1]에서 두 요소의 합이 배열 안에
// 존재하는 고유한 쌍의 개수를 반환
int countpairs(int ar[], int n){
// 맵 m에 모든 요소의 등장 횟수를 저장
// (ar[i]) + (sum - ar[i]) = sum 이므로
// 쌍 (ar[i], sum-ar[i])을 찾는 데 활용
map<int, int> mymap;
for (int i = 0; i < n; i++){
mymap[ar[i]]++;
}
// 중복 항목 제거를 위해 결과용 맵 사용
map<pair<int, int>, int> p;
int result = 0;
// 모든 가능한 쌍을 검사
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
// 현재 쌍의 합이 배열에 존재하는 경우
if (mymap[ar[i] + ar[j]] > 0 && p[{ ar[i], ar[j] }] == 0){
result++;
}
// 현재 쌍을 양방향으로 삽입하여
// 중복 카운트 방지
p[{ ar[i], ar[j] }][]++;
p[{ ar[j], ar[i] }][]++;
}
}
return result;
}
// 메인 함수
int main(){
int ar[] = { 6, 4, 10, 14 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << "count is " << countpairs(ar, n);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻습니다.
count is 2