양의 정수로 이루어진 두 개의 배열과 값 K가 주어집니다. 목표는 첫 번째 배열의 요소 A와 두 번째 배열의 요소 B로 구성된 고유한 쌍 (A, B) 중에서 A % B = K 또는 B % A = K를 만족하는 쌍의 개수를 구하는 것입니다.
예시로 이해하기
입력 − arr_1[] = {1,2,5,3,4}; arr_2[] = {7,1,3}; k=2
출력 − 모듈로 연산 결과가 K가 되는 두 배열의 쌍 개수: 2
설명 − 해당 쌍은 (5,7), 즉 (arr_1[2], arr_2[1])로 7%5=2이며, (5,3), 즉 (arr_1[2], arr_2[2])로 5%3=2입니다.
입력 − arr_1[] = {2,5}; arr_2[] = {3,7}; k=1
출력 − 모듈로 연산 결과가 K가 되는 두 배열의 쌍 개수: 2
설명 − 해당 쌍은 (2,3), 즉 (arr_1[0], arr_2[0])으로 3%2=1이며, (2,7), 즉 (arr_1[0], arr_2[1])로 7%2=1입니다.
프로그램에 사용된 접근 방식
이 접근 방식에서는 for 루프를 사용해 두 배열을 모두 순회합니다. A%B=k 또는 B%A=k를 만족하는 쌍(A는 arr_1에 속하고 B는 arr_2에 속함)을 set<pair<int, int>> 타입의 컨테이너 se에 삽입합니다. set은 중복 요소를 자동으로 제거하므로, 최종적으로 se의 크기(size)가 곧 조건을 만족하는 고유한 쌍의 개수가 됩니다.
양의 정수 요소를 가진 배열 arr_1[]과 arr_2[], 그리고 각각의 길이 size_arr_1, size_arr_2를 준비합니다.
정수 k를 입력받습니다.
modulo_pairs(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int k) 함수는 두 배열과 각 길이를 인자로 받아, 두 배열 요소의 모듈로 연산 결과가 k가 되는 쌍의 개수를 반환합니다.
count의 초기값을 0으로 설정합니다.
조건을 만족하는 쌍을 저장하기 위해 set<pair<int, int>> se를 선언합니다.
i=0부터 i<size_arr_1까지 arr_1[]을, j=0부터 j<size_arr_2까지 arr_2[]를 순회합니다.
각 쌍 (arr_1[i], arr_2[j])에 대해 arr_1[i] > arr_2[j]라면 arr_1[i] % arr_2[j] == k 여부를 확인하고, 참이면 이 쌍을 set se에 삽입합니다.
그렇지 않은 경우(arr_1[i] ≤ arr_2[j])에는 arr_2[j] % arr_1[i] == k 여부를 확인하고, 참이면 이 쌍을 set se에 삽입합니다.
count를 se.size()로 계산하여 고유한 쌍의 개수를 구합니다.
count를 결과로 반환합니다.
예제
#include <bits/stdc++.h>
using namespace std;
int modulo_pairs(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int k){
int count = 0;
set<pair<int, int>> se;
for (int i = 0; i < size_arr_1; i++){
for (int j = 0; j < size_arr_2; j++){
if (arr_1[i] > arr_2[j]){
if (arr_1[i] % arr_2[j] == k){
se.insert(make_pair(arr_1[i], arr_2[j]));
}
}
else{
if (arr_2[j] % arr_1[i] == k){
se.insert(make_pair(arr_2[j], arr_1[i]));
}
}
}
}
count = se.size();
return count;
}
int main(){
int arr_1[] = { 2, 7, 1, 9 };
int arr_2[] = { 4, 10, 3, 10 };
int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]);
int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]);
int k = 3;
cout<<"모듈로 연산 결과가 K가 되는 두 배열의 쌍 개수:"<<modulo_pairs(arr_1, arr_2, size_arr_1, size_arr_2, k);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
모듈로 연산 결과가 K가 되는 두 배열의 쌍 개수: 2