C 언어로 첫 번째 배열의 최댓값과 두 번째 배열의 최솟값 곱 구하기

문제 개요

크기가 각각 n1과 n2인 두 개의 배열 arr1[]과 arr2[]가 주어졌을 때, 첫 번째 배열 arr1[]의 최댓값과 두 번째 배열 arr2[]의 최솟값을 곱한 결과를 구하는 것이 이번 문제의 목표입니다.

예를 들어 arr1[] = {5, 1, 6, 8, 9}이고 arr2[] = {2, 9, 8, 5, 3}이라면, arr1의 최댓값은 9이고 arr2의 최솟값은 2이므로 두 값의 곱은 9 × 2 = 18이 됩니다. 이처럼 주어진 문제를 해결하는 프로그램을 작성해 보겠습니다.

입력 예시 1

arr1[] = {6, 2, 5, 4, 1}
arr2[] = {3, 7, 5, 9, 6}

출력

설명

MAX(arr1) * MIN(arr2) → 6 * 3 = 18

입력 예시 2

arr1[] = {2, 3, 9, 11, 1}
arr2[] = {5, 4, 2, 6, 9}

출력

설명

MAX(arr1) * MIN(arr2) → 11 * 2 = 22

문제 해결 접근 방식

두 배열 arr1과 arr2를 입력으로 받습니다.
두 배열을 모두 오름차순으로 정렬합니다.
정렬된 arr1의 마지막 요소(최댓값)와 arr2의 첫 번째 요소(최솟값)를 곱합니다.
계산된 곱을 결과로 반환합니다.

알고리즘

시작
함수 int sortarr(int arr[], int n)
    단계 1→ temp 변수를 선언하고 초기화한다
    단계 2→ i = 0부터 i < n-1까지 ++i 반복
        j = i+1부터 j < n까지 j++ 반복
            만약 arr[i] > arr[j]라면
                temp ← arr[i]
                arr[i] ← arr[j]
                arr[j] ← temp
함수 int minMaxProduct(int arr1[], int arr2[], int n1, int n2)
    단계 1→ sortarr(arr1, n1) 호출
    단계 2→ sortarr(arr2, n2) 호출
    단계 3→ (arr1[n1 - 1] * arr2[0]) 반환
함수 int main()
    단계 1→ arr1[] = {2, 3, 9, 11, 1} 선언 및 초기화
    단계 2→ arr2[] = {5, 4, 2, 6, 9} 선언 및 초기화
    단계 3→ n1, n2를 선언하고 각 배열의 크기로 초기화
    단계 4→ minMaxProduct(arr1, arr2, n1, n2) 출력
종료

예제 코드

#include <stdio.h>

int sortarr(int arr[], int n){
   int temp;
   for (int i = 0; i < n-1; ++i){
      for(int j = i+1; j<n; j++){
         if(arr[i]> arr[j]){
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
         }
      }
   }
   return 0;
}

int minMaxProduct(int arr1[], int arr2[], int n1, int n2){
   // 최댓값과 최솟값을 구하기 위해 배열을 정렬합니다.
   sortarr(arr1, n1);
   sortarr(arr2, n2);
   // 최댓값과 최솟값의 곱을 반환합니다.
   return arr1[n1 - 1] * arr2[0];
}

int main(){
   int arr1[] = { 2, 3, 9, 11, 1 };
   int arr2[] = { 5, 4, 2, 6, 9 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   int n2 = sizeof(arr2) / sizeof(arr2[0]);
   printf("%d\n", minMaxProduct(arr1, arr2, n1, n2));
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

시간 복잡도와 개선 방안

위 코드는 선택 정렬 방식으로 배열을 정렬하기 때문에 시간 복잡도는 O(n²)입니다. 정렬 없이 각 배열을 한 번만 순회하면서 최댓값과 최솟값을 직접 찾으면 O(n1 + n2) 시간 안에 더 효율적으로 문제를 해결할 수 있습니다.

int minMaxProduct(int arr1[], int arr2[], int n1, int n2){
   int max1 = arr1[0], min2 = arr2[0];
   for (int i = 1; i < n1; i++)
      if (arr1[i] > max1)
         max1 = arr1[i];
   for (int i = 1; i < n2; i++)
      if (arr2[i] < min2)
         min2 = arr2[i];
   return max1 * min2;
}

이 방식은 불필요한 정렬 과정을 생략하므로 배열의 크기가 커질수록 성능 차이가 더욱 벌어집니다. 실무에서는 상황에 따라 정렬 기반 방식과 선형 탐색 방식 중 적절한 것을 선택하면 됩니다.