Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 배열에서 쌍의 곱이 배열 안에 존재하는 쌍의 개수 구하기

문제 개요

정수형 요소로 이루어진 배열이 주어졌을 때, 배열의 요소들로 쌍(pair)을 만들고 각 쌍의 곱을 계산한 뒤, 그 곱이 원래 배열 안에 존재하는지 확인하는 것이 이번 문제의 목표입니다.

입력 − int arr[] = {6, 2, 3, 1, 5, 10}

출력 − 곱이 같은 배열에 존재하는 쌍의 개수 − 7

설명 − 주어진 배열에서 만들 수 있는 쌍은 (6, 2), (6, 3), (6, 1), (6, 5), (6, 10), (2, 3), (2, 1), (2, 5), (2, 10), (3, 1), (3, 5), (3, 10), (1, 5), (1, 10), (5, 10)입니다. 이 중 곱이 같은 배열에 존재하는 쌍은 (2, 3)의 곱 6, (6, 1)의 곱 6, (3, 1)의 곱 3, (2, 5)의 곱 10, (1, 5)의 곱 5, (2, 1)의 곱 2, (1, 10)의 곱 10으로 총 7개입니다.

입력 − int arr[] = {2, 4, 8, 5, 10}

출력 − 곱이 같은 배열에 존재하는 쌍의 개수 − 2

설명 − 주어진 배열에서 만들 수 있는 쌍은 (2, 4), (2, 8), (2, 5), (2, 10), (4, 8), (4, 5), (4, 10), (8, 5), (8, 10), (5, 10)입니다. 이 중 곱이 같은 배열에 존재하는 쌍은 (2, 4)의 곱 8, (2, 5)의 곱 10으로 총 2개입니다.

단순 접근 방식(Naive Approach)

주어진 문제는 여러 가지 방법으로 해결할 수 있으며, 대표적으로 단순 접근 방식과 효율적인 접근 방식이 있습니다. 먼저 단순 접근 방식부터 살펴보겠습니다.

  • 정수 요소로 이루어진 배열을 입력받고, 배열의 크기를 계산한 후 함수에 전달합니다.
  • 곱이 배열에 존재하는 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
  • i를 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
  • 루프 안에서 j를 i + 1부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
  • 루프 안에서 product = arr[i] * arr[j]로 곱을 계산합니다.
  • k를 0부터 배열 크기까지 반복하는 FOR 루프를 하나 더 시작합니다.
  • k 루프 안에서 product == arr[k]인지 확인하고, 조건이 참이면 count를 1 증가시킵니다.
  • count를 반환합니다.
  • 결과를 출력합니다.

이 방식은 세 겹의 중첩 루프를 사용하므로 시간 복잡도는 O(n³)입니다.

효율적인 접근 방식(Efficient Approach)

효율적인 접근 방식에서는 STL의 set 자료구조를 활용해 특정 값의 존재 여부를 빠르게 확인합니다. set의 find 함수는 O(log n) 시간에 동작하므로 전체 시간 복잡도를 O(n² log n)까지 줄일 수 있습니다.

  • 정수 요소로 이루어진 배열을 입력받고, 배열의 크기를 계산한 후 함수에 전달합니다.
  • 곱이 배열에 존재하는 쌍의 개수를 저장할 임시 변수 count를 선언합니다.
  • STL set 타입의 변수 pro를 생성합니다.
  • i를 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
  • 루프 안에서 set 변수 pro에 arr[i]를 삽입합니다.
  • i를 0부터 배열 크기까지 반복하는 FOR 루프를 다시 시작합니다.
  • 루프 안에서 j를 i + 1부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
  • product를 arr[i] * arr[j]로 설정합니다.
  • pro.find(product) != pro.end()인지 확인하고, 조건이 참이면 count를 1 증가시킵니다.
  • count를 반환합니다.
  • 결과를 출력합니다.

예제 코드 (단순 접근 방식)

#include <bits/stdc++.h>
using namespace std;
int product_pair(int arr[], int size){
    int product = 1;
    int count = 0;
    for(int i = 0 ; i<size ; i++){
        for(int j = i+1;j<size;j++){
            product = arr[i] * arr[j];
            for(int pro = 0 ; pro < size; pro++){
                if(product == arr[pro]){
                    count++;
                }
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {6, 2, 3, 1, 5, 10};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of pairs whose products exist in same array are: "<<product_pair(arr,size);
    return 0;
}

출력

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

Count of pairs whose products exist in same array are: 7

예제 코드 (효율적인 접근 방식)

#include<bits/stdc++.h>
using namespace std;
int product_pair(int arr[], int size){
    set< int > pro;
    int count = 0;
    int product = 1;
    for (int i = 0 ; i < size; i++){
        pro.insert(arr[i]);
    }
    for (int i = 0 ; i < size; i++){
        for (int j = i + 1; j < size ; j++){
            product = arr[i] * arr[j];
            if(pro.find(product) != pro.end()){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {6, 2, 3, 1, 5, 10};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of pairs whose products exist in same array are: "<<product_pair(arr,size);
    return 0;
}

출력

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

Count of pairs whose products exist in same array are: 7