C++로 배열에서 a % b = k를 만족하는 모든 쌍 (a, b) 찾기

배열 A가 주어졌을 때, 배열의 원소들 중에서 a % b = k 조건을 만족하는 모든 쌍 (a, b)을 찾아야 합니다.

예를 들어 배열이 A = [2, 3, 4, 5, 7]이고 k = 3이라면, 조건을 만족하는 쌍은 (7, 4), (3, 4), (3, 5), (3, 7)입니다. 각 쌍에서 첫 번째 원소를 두 번째 원소로 나눈 나머지가 정확히 k가 되는지 확인하면 됩니다.

해결 접근 방식

이 문제는 비교적 단순한 방법으로 해결할 수 있습니다. 배열의 모든 원소 쌍을 순회하면서 각 쌍에 대해 나머지 연산 결과가 k와 일치하는지 검사하고, 일치하는 경우 해당 쌍을 출력하면 됩니다.

구체적인 알고리즘은 다음과 같습니다.

1. 두 개의 중첩 반복문을 사용하여 배열의 모든 순서쌍 (arr[i], arr[j])을 생성합니다.
2. arr[i] % arr[j] == k 조건을 검사합니다.
3. 조건을 만족하면 해당 쌍을 출력합니다.
4. 조건을 만족하는 쌍이 하나도 없다면 "쌍을 찾을 수 없음" 메시지를 출력합니다.

예제 코드

#include <iostream>
using namespace std;
bool displayPairs(int arr[], int n, int k) {
   bool pairAvilable = true;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         if (arr[i] % arr[j] == k) {
            cout << "(" << arr[i] << ", "<< arr[j] << ")"<< " ";
            pairAvilable = true;
         }
      }
   }
   return pairAvilable;
}
int main() {
   int arr[] = { 2, 3, 4, 5, 6, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   if (displayPairs(arr, n, k) == false)
      cout << "No paira found";
}

실행 결과

(3, 4) (3, 5) (3, 6) (3, 7) (7, 4)

코드 설명

위 코드에서 displayPairs 함수는 배열과 배열 크기 n, 그리고 목표 나머지 값 k를 매개변수로 받습니다. 이중 반복문을 통해 배열의 모든 쌍을 검사하며, 나머지 연산 결과가 k와 같으면 해당 쌍을 화면에 출력합니다.

배열 {2, 3, 4, 5, 6, 7}에서 k = 3인 경우를 살펴보면, 3을 4, 5, 6, 7로 나누면 모두 나머지가 3이 되므로 (3, 4), (3, 5), (3, 6), (3, 7) 쌍이 출력됩니다. 또한 7을 4로 나누면 나머지가 3이 되므로 (7, 4) 쌍도 결과에 포함됩니다.

시간 복잡도

이 방법은 모든 가능한 쌍을 검사하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 작거나 중간 정도일 때는 충분히 효율적이지만, 배열이 매우 큰 경우에는 최적화된 알고리즘을 고려해야 할 수 있습니다.