C++에서 주어진 합이 되는 쌍의 개수 세기

정수 배열과 목표 합(sum)이 주어졌을 때, 배열의 서로 다른 두 원소를 짝지어 그 합이 목표 값과 정확히 일치하는 쌍(pair)이 총 몇 개인지 구하는 것이 이번 문제의 과제입니다.

예제 1

입력 − int arr[] = {2, 8, 1, 5, 11}, sum = 13

출력 − 합이 13이 되는 쌍의 개수: 2

설명 − 배열에서 만들 수 있는 모든 쌍과 각각의 합은 다음과 같습니다.

합이 13이 되는 쌍은 (2, 11)과 (8, 5)로 총 2개입니다.

예제 2

입력 − int arr[] = {2, 8, 1, 5, -11}, sum = 6

출력 − 합이 6이 되는 쌍의 개수: 1

설명 −

합이 6이 되는 쌍은 (1, 5) 하나뿐입니다.

프로그램에서 사용된 접근 방식

• 쌍을 만들 정수 배열과 목표 합의 정숫값을 입력받습니다.
• 배열의 크기를 계산한 뒤, 이후 처리를 위해 배열·크기·합을 함수에 전달합니다.
• 조건에 맞는 쌍의 개수를 저장할 임시 변수 count를 준비합니다.
• i를 0부터 배열 크기까지 반복하는 바깥쪽 FOR 루프를 시작합니다.
• 루프 안에서 j를 i+1부터 배열 크기까지 반복하는 안쪽 FOR 루프를 시작합니다.
• 루프 내부에서 임시 변수 total을 arr[i] + arr[j]로 설정합니다.
• total == sum인지 검사하여 참이면 count를 1 증가시킵니다.
• 모든 반복이 끝나면 count를 반환합니다.
• 결과를 화면에 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
//주어진 합이 되는 쌍의 개수 세기
int Pair_Sum(int arr[], int size, int sum){
    int count = 0;
    for (int i=0; i<size; i++){
       for (int j=i+1; j<size; j++){
          int total = arr[i] + arr[j];
          if (total == sum){
             count++;
          }
       }
    }
    return count;
}
int main(){
    int arr[] = {2, 6, 1, 7, 9, 8} ;
    int sum = 9;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of pairs with given sum "<<sum<<" is: "<<Pair_Sum(arr, size, sum);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

Count of pairs with given sum 9 is: 2

시간 복잡도

위 구현은 두 개의 중첩 루프로 배열 내 모든 쌍을 하나씩 확인하므로, 배열의 크기가 n일 때 시간 복잡도는 O(n²)입니다. unordered_map과 같은 해시 기반 자료구조를 활용해 각 원소의 짝이 되는 값(sum − 현재 값)이 이미 등장했는지 확인하면, 한 번의 순회만으로 O(n)까지 성능을 개선할 수 있습니다.